fucking-algorithm
fucking-algorithm copied to clipboard
Published
20 hours ago •
labuladong
labuladong
递归魔法：反转单链表 :: labuladong的算法小抄
@GeorgeSmith215 @dullduck 是这个意思，这是递归对数据结构进行修改的常见操作，head.next 必须接收对 head.next 的递归返回值，否则无法做到修改链表结构的作用。类似的，你去看 BST 的增删查改，都是这种模式。
public static ListNode reverseNM(ListNode current,int n,int m) {
ListNode last = current; // 前一部分的最后一个节点，注意是前一部分，而不是交换部分
while(n>2) {
last = last.next; // 进行条件的设定，因为要记录下第n的前一个，方便链接最后反转后的头节点，要记录下当前的为n==1，前一个为>2
n--;
}
last.next = reverseN(last.next,m-n);
return current;
}
博主你好，请问一下，反转部分链表的时候，直接使用一个迭代，得到需要反转部分的前一个，然后在进行操作，这种方式合理吗，还是按照博主你的来，我发现思路有点混乱
标题：“二、反转链表前 N 个节点”最后的代码我认为还可以优化一下 源代码：
ListNode successor = null; // 后驱节点
// 反转以 head 为起点的 n 个节点，返回新的头结点
ListNode reverseN(ListNode head, int n) {
if (n == 1) {
// 记录第 n + 1 个节点
successor = head.next;
return head;
}
// 以 head.next 为起点，需要反转前 n - 1 个节点
ListNode last = reverseN(head.next, n - 1);
head.next.next = head;
// 让反转之后的 head 节点和后面的节点连起来
head.next = successor;
return last;
}
优化后的代码：
// 反转以 head 为起点的 n 个节点，返回新的头结点
ListNode reverseN(ListNode head, int n) {
if (n == 1) {
// 返回最后头节点
return head;
}
// 以 head.next 为起点，需要反转前 n - 1 个节点
ListNode last = reverseN(head.next, n - 1);
/*
这里意思是，head的next指针没有啥用，可以用来记录第n+1个节点，随着递归一直往上传到原来头节点的next。（可以自己画图，比较好理解一点）
*/
ListNode headNext = head.next;
head.next = headNext.next;
headNext.next = head;
return last;
}
个人理解
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
last = self.reverseList(head.next)
# 在递归返回的时候，元素“天然”地会倒序弹出
head.next.next = head # 完成head和它后一个节点（head.next）的反转
head.next = None # 原本的下一个节点置空，避免两个节点互为next死循环
return last # 不论当前节点是啥，都返回原本链表的最后一个节点-》也就是反转后的头节点
js 版
function ListNode(val, next) {
this.val = val === undefined ? 0 : val;
this.next = next === undefined ? null : next;
}
function buildLinkList(values) {
return values.reverse().reduce((acc, val) => new ListNode(val, acc), null);
}
// ---- Generate our linked list ----
const linkedList = buildLinkList([1, 2, 3, 4, 5, 6]);
let count = 0;
function log(n, message, obj = null) {
if (typeof obj === "object" && obj !== null) {
obj = JSON.stringify(obj);
}
console.log(new Array(n < 0 ? 0 : n).fill(" ").join(""), message, obj);
}
var reverseList = function (head) {
return reverse(head);
function reverse(node) {
// log(count++, "node", node);
if (node === null || node.next === null) {
return node;
}
const last = reverse(node.next);
// log(count, "node", node);
node.next.next = node;
node.next = null;
// log(count--, "last", last);
return last;
}
};
function reverseN(head, n) {
let successor = null;
return reverse(head, n);
function reverse(node, n) {
// log(count++, "node", node);
if (n === 1) {
successor = node.next;
return node;
}
const last = reverse(node.next, n - 1);
// log(count++, "node", node);
node.next.next = node;
node.next = successor;
// log(count--, "last", last);
return last;
}
}
var reverseBetween = function (head, left, right) {
// base case
if (left === 1) {
return reverseN(head, right);
}
// 前进到反转的起点触发 base case
head.next = reverseBetween(head.next, left - 1, right - 1);
return head;
};
console.log(JSON.stringify(reverseBetween(linkedList, 2, 4), null, 2));
Java代码注释版
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode last = reverseList(head.next); // 最深处的last会到达最后一个节点
head.next.next = head; // 让下一个节点的next指向自己
head.next = null; // 自己的next废弃掉
return last; // 返回的是最深处的last，也就是原链表的最后一个节点
}
}
https://stackoverflow.com/questions/37848186/how-to-understand-head-next-next-head-for-reverse-single-list-by-recursion
C++版本
ListNode* reverseBetween(ListNode* head, int left, int right) {
// base case:
if (left == 1) return reverseK(head, right);
// recursive
ListNode* reverseHead = reverseBetween(head->next, left - 1, right - 1);
head->next = reverseHead;
return head;
}
ListNode* reverseK(ListNode* head, int k) {
// base case:
if (k == 1) return head;
// recursive
ListNode* reverseHead = reverseK(head->next, k - 1);
ListNode* successor = head->next->next;
// reverse the link:
head->next->next = head;
// connect to the successor:
head->next = successor;
return reverseHead;
python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def __init__(self):
self.successor=None
#翻转前N个
def reverseN(self, head, n):
if n==1:
self.successor=head.next
return head
last=self.reverseN(head.next,n-1)
head.next.next=head
head.next=self.successor
return last
def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
if left==1:
return self.reverseN(head,right)
head.next=self.reverseBetween(head.next,left-1,right-1) # head向后移了一位，所以链表总长度-1，所以right-1
return head
其实要理解递归那个，如果直接看理解不了，可以从base case也就是head.next==null往前推几个node，就能理解递归的设计思路了 last只负责一直指向最后一个节点，下面的head.next.next = head; head.next = null;才是实现反转的，每返回一次head往前回退一个node
感谢博主的笔记～
