递归魔法：反转单链表 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：递归魔法：反转单链表

评论礼仪 见这里，违者直接拉黑。

[DA-MO-WANG]

看完了，大魔王到此一游

[WuDaoJiuXiao]

众所周知，任用迭代，神用递归

[dullduck]

head.next = reverseBetween(head.next, m - 1, n - 1);

[dullduck]

head.next = reverseBetween(head.next, m - 1, n - 1);
这里的左值为何是head.next呢？

[coderZoe]

相当于取当前完整链表的子链表，这个子链表就是去掉当前链表的头，也即链表一直去头，直到那个头就是起始的反转节点为止。

[CarlLy7]

我是这样理解的，因为我们的base case是从第一个节点开始反转n个节点，head.next相当于让当前的节点依次往前移动，往前移动一个位置，那么起始索引和终止索引对于移动之后的这个索引来说就是-1了

[GeorgeSmith215]

@dullduck
我觉得应该是要让不需要反转的最后一个结点的next指针指向已经逆转并返回的头结点，不然链表会断

[fkgogo123]

if (m == 1) {
// 相当于反转前 n-m+1 个元素
return reverseN(head, n-m+1);

[labuladong]

@GeorgeSmith215 @dullduck 是这个意思，这是递归对数据结构进行修改的常见操作，head.next 必须接收对 head.next 的递归返回值，否则无法做到修改链表结构的作用。类似的，你去看 BST 的增删查改，都是这种模式。

[YoucanBaby]

这递归写得好漂亮

[zhuifengshaonian201]

讲的真好

[luckywords]

	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;
	}

博主你好，请问一下，反转部分链表的时候，直接使用一个迭代，得到需要反转部分的前一个，然后在进行操作，这种方式合理吗，还是按照博主你的来，我发现思路有点混乱

[wqy71]

这样也是可以的。

[wqy71]

相当于找到要反转的部分链表的前一个节点，然后取这个节点的next做反转前n个节点。

[yxw007]

我也是这么思考的，把结果分享给你

var reverseBetween = function (head, left, right) {
  /**
   * 反转前n个节点
   * @param {*} head
   * @param {*} n
   */
  var reverseN = function (head, n) {
    let lastNode = null;
    function reverse(head, n) {
      if (head == null || head.next == null || n == 0) {
        return head;
      }
      if (n == 1) {
        lastNode = head.next;
        return head;
      }

      let last = reverse(head.next, n - 1);
      head.next.next = head;
      head.next = lastNode;

      return last;
    }

    return reverse(head, n);
  };

  let n = right - left + 1;
  if (n <= 1) {
    return head;
  }

  //! 说明：如果要从第一个节点反转，就会导致第一个节点无法反转，所以需要一个dummyHead
  let dummyHead = new ListNode(null, head);
  let p = dummyHead;
  let i = left;
  //! 找到left的前一个节点，比如：left=2 , 2>1 就是移动1步
  while (i > 1) {
    p = p.next;
    i--;
  }
  let preHead = p;
  //! 反转preHead.next 后面的n个节点
  let tail = reverseN(preHead.next, n);
  preHead.next = tail;

  return dummyHead.next;
};

[xiaobie1900]

标题：“二、反转链表前 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;
}

[hemw]

感觉这个是错的

[tonywan96]

牛蛙牛蛙

[yangchongluo]

太牛了吧

[wing7171]

理解递归函数的定义并不难，我觉得难点在于，理解它为什么可以做到这样的功能…

[wing7171]

个人理解

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 # 不论当前节点是啥，都返回原本链表的最后一个节点-》也就是反转后的头节点

[CC-Halen]

找到递归的base case，通过递归逐步逼近base case

[Jiameng991010]

普通人只会迭代，大神只用递归。哭死

[twotwoba]

有时候迭代可比递归难

[huanghao7414]

怎么写出来这么牛逼的代码？

[lambdaxing]

C++ 的反转链表2 迭代版：

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode dummy;
        dummy.next = head;
        ListNode *before = &dummy, *pre = head, *cur = head->next;
        for(int i = 1; i < left; i++) {
            before = pre;
            pre = cur;
            cur = cur->next;
        }

        while(cur != nullptr && left < right) {
            left++;
            ListNode *next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }

        before->next->next = cur;
        before->next = pre;

        return dummy.next;
    }
};

[JohnHwangzn]

通过明确递归函数的定义来解决递归问题, 而不要跳进递归，这个思想很有帮助 ! 一旦陷入递归, 思维就很会一团乱麻.

[ReAllTh]

反转链表前 N 个节点

---

虽说 不要跳进递归，而是利用明确的定义来实现算法逻辑。
但是我自己作为算法新人，开始的时候对于

    if (n == 1) {
        // 记录第 n + 1 个节点
        successor = head.next;
        return head;
    }

只有跳进递归才能理解 successor = head.next 的作用
因为按照 明确的定义 来说 n = 1 时只有一个节点，直接返回这个节点即可，successor = head.next 是不必要的

---

后来转念一想，n = 1 时其实是在 翻转前 N 个节点的最后一个节点，而 只有一个节点存在 只是它的一个特殊情况
这样，successor = head.next 就能说通了：在翻转前 N 个节点的最后一个节点的时候记录第 N + 1 个节点

对递归的理解又加深了一点:v:

[CarlLy7]

666，这个大boss的往前走的思想真的不容易想出来啊

[icode36]

引用原文：迭代实现思路看起来虽然简单，但是细节问题很多的，反而不容易写对。
评论：太对了，稍复杂点的链表反转，迭代边界条件很容易犯错。总得提交几次才能Accepted

[zhangshuolei-hfut]

哈哈，一开始不会迭代反转单链表，又去查了一下。现在两者皆会了。

[niuqitong]

beautiful

[hwaphon]

真烧脑，看了两遍还懵懵懂懂，我太菜了😭

[anglelikepupu]

Day2打卡！

[JeanYang2]

92.反转链表Python版本打卡

class Solution:
    def __init__(self):
        self.successor=ListNode()

    def reverseN(self,head: Optional[ListNode],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: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        if left==1:
            return self.reverseN(head,right)
        head.next=self.reverseBetween(head.next,left-1,right-1)
        return head

[fear666]

反转链表前N个结点

不需额外记录后继结点的写法

func reverseN(head *ListNode, n int) *ListNode {
  if n == 1 { //base case
    return head
  }

  reverseHead := reverseN(head.Next, n-1)
  tmp := head.Next.Next
  head.Next.Next = head
  head.Next = tmp

  return reverseHead
}

[Suntaoning]

感觉可以使用链表的头插法用来翻转链表吧，如果使用头插法，仅需一个for循环，而不用递归。

[zshuang111]

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.next = successor; 这行去掉，在最后返回的时候执行 head.next = successor; 这样是不是也可以的？