Dec 16, 2020

颠三倒四的链表

链表的反转

反转一个单链表

示例:

输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/reverse-linked-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

迭代解

维护一个前驱节点 pre，这个节点永远是当前迭代节点的前一个节点，初始化值是 null，反转之后的链表最后一个节点指向的就是这个 null
把 head 作为当前节点的指针
迭代
当 head 变成null时，迭代退出
保存当前节点的下一个节点 head.next
把当前节点指向前一个节点 head -> pre
把 pre 和 head 向前移动一步
返回迭代后的 pre 节点，即反转后的链表的最后一个节点

代码实现

var reverseList = function(head) {
    let pre = null

    while(head) {
        let next =  head.next
        head.next = pre
        pre = head
        head = next
    }

    return pre
};

时间复杂度：O(n) 空间复杂度：O(1)

递归解

递归的代码很简洁，总体思路是：

首先定义递归返回条件，对反转链表来说，当前节点是null或者只有一个节点（下一个节点为null），就说明没必要反转，直接返回这个节点就好

var reverseList = function(head) {
    if(!head || head.next == null) return head

   //...
};

递归调用 reverseList，传入下一个节点（head.next）, 返回的值就是结束节点到 head.next 节点的整个链表反转结果。这里要注意不要尝试用人脑递归理解，逻辑推理一下，我们的 reverserList 方法，功能就是传入一个链表，把它反转之后返回，所以，只要从逻辑上把握这个含义就好，不然人脑很快就栈溢出了。

var reverseList = function(head) {
    if(!head || head.next == null) return head

    let newHead = reverseList(head.next)

//...
};

好了，做完上面这一步，我们手上有一个 head 节点，和一个已经反转好的结束节点到 head.next 节点的链表，很明显我们要做的有两件事：

把 head.next 指向head
把 head 指向 null

最后，返回新的头节点，大功告成！

代码实现

var reverseList = function(head) {
    if(!head || head.next == null) return head

    let newHead = reverseList(head.next)
    head.next.next = head
    head.next = null
    
    return newHead
};

时间复杂度：O(n) 空间复杂度：O(n)

反转链表 m —> n

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明: 1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/reverse-linked-list-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

上一题是是反转整条链表，这一题是反转 m -> n , 我们可以利用一样的反转的原理，大致的思路是：

先把指针移动到 m 的前一个节点，
循环执行 n - m 次反转逻辑（这一步的逻辑和上一题一样）
把 m -1 和反转后的头节点相连，把反转后的尾节点和 n + 1 相连

代码实现

var reverseBetween = function(head, m, n) {
  // new一个新的节点，把原始的头节点保存下来
    let originalHead = new ListNode()
    originalHead.next = head

  // 申明一个临时节点，并移动到 m-1 的位置
    let tempHead = originalHead

    for(let i = 0; i < m - 1; i++) {
        tempHead = tempHead.next
    }

 // 这一步开始和反转链表，核心逻辑和上一题一致
    let pre = tempHead
    let cur = tempHead.next
    let first = cur // 保存第一个节点的引用，这个节点反转后就变成了最后一个节点，后面要连接这个节点和 n + 1 个节点

    for(let j = 0; j < n - m + 1; j++) {
        let next = cur.next
        cur.next = pre
        pre = cur
        cur = next
    }

   // 反转的逻辑结束，这时候m -> n的节点已经成功反转
 // 连接第m - 1个节点和反转后的第一个节点
   tempHead.next = pre
   // 连接反转后的尾巴节点和第 n+1 个节点，这时候 cur 就是第 n+1 个节点，因为循环结束后，cur 就变成了 n+1 的节点
   first.next = cur
    
   // 返回保存的原始头节点
   return originalHead.next
};

时间复杂度： O(n) 空间复杂度： O(1)

K 个一组翻转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例：

给你这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明：

你的算法只能使用常数的额外空间。你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

整体思路是把整个链表分成若干个 K 个一组的小单位，逐个小单位反转并连接好小单位的前后节点。

代码实现

var reverseKGroup = function(head, k) {
    // 保存一个原始的头节点，最终返回的
    let originalHead = new ListNode()
    originalHead.next = head
    
   // 维护两个指针，start 和 end，用来定位每个小单位
    let [start,end] = [originalHead,originalHead.next]
  // 维护一个计数变量，移动指针的时候和 K 取余，判断是否到达 K 个
    let count = 0

    while(end) {
        count++
        if(count % k === 0) {
            // 分组完成，反转节点，并确定下一步的重置指针
            start = reverseList(start, end.next)
            end = start.next
        } else {
  // 分组未完成，end指针向后移动一位
            end = end.next
        }
    }

    return originalHead.next

    // 反转链表的方法：注意，传入的是开始节点的**前一个节点**和结束节点的**后一个节点**，是为了可以在反转后拼接该小单位的前后节点
    function reverseList(start,end) {
        let [pre,cur] = [start,start.next]
        let firstNode = cur
        
        while(cur !== end) {
            let next = cur.next
            cur.next = pre
            pre = cur
            cur = next
        }

        start.next = pre
        firstNode.next = cur

        return firstNode
    }
};

时间复杂度： O(n) 空间复杂度： O(1)