链表学习总结

参考文章：

• 链表专题 - 力扣加加 - 努力做西湖区最好的算法题解

总结

（转自参考文章）

• 一个原则：多画图
• 两个考点：指针的修改，链表的拼接
• 三个注意：
  1. 环（由于操作顺序等问题，或者特殊情况没考虑到，导致出现环）
  2. 边界
  3. 前后序 （这个我倒是不太理解）
• 技巧：
  1. 虚拟头：如果头节点可能发生修改
  2. 快慢指针：适用于部分题型

常用操作

反转链表

• 206. 反转链表 - 力扣（LeetCode）
• 【反转链表】：双指针，递归，妖魔化的双指针

这个问题的关键就是now.next = before （反转操作时），now.next 会丢失，所以需要一个额外的变量保存这个值。

方法一：

（图源LeetCode优质题解，下同）

// 双指针法
public ListNode reverseList(ListNode head) {
    ListNode tail = null;
    ListNode tmp = null;
    while(head != null) {
        tmp = head.next;
        head.next = tail;
        tail = head;
        head = tmp;
    }
    return tail;
}

方法二：

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) {return null;}
        ListNode cur = head;
        ListNode tmp = null;
        // 注意这里有可能head是null，所以要在前面做一个判断
        while(head.next != null) {
            tmp = head.next.next;

            head.next.next = cur;
            cur = head.next;
            
            head.next = tmp;
        }

        return cur;
    }
}

方法三：递归：

这个要递归调用，内存开销会大一点吧（那还不如借助栈？）

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode tmp = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return tmp;
    }
}

递归

• 24. 两两交换链表中的节点 - 力扣（LeetCode）

1. 找终止条件：本题终止条件很明显，当递归到链表为空或者链表只剩一个元素的时候，没得交换了，自然就终止了。
2. 找返回值：返回给上一层递归的值应该是已经交换完成后的子链表。
3. 单次的过程：因为递归是重复做一样的事情，所以从宏观上考虑，只用考虑某一步是怎么完成的。我们假设待交换的俩节点分别为head和next，next的应该接受上一级返回的子链表(参考第2步)。就相当于是一个含三个节点的链表交换前两个节点，就很简单了，想不明白的画画图就ok。

（源题目评论）

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode next = head.next;
        head.next = swapPairs(next.next);
        next.next = head;
        return next;
    }
}

• 25. K 个一组翻转链表 - 力扣（LeetCode）

这个题结合了206. 翻转链表和24. 两两交换链表中的节点，由于对每一段的处理有重复的部分，所以考虑用递归。

递归三要素：

1. 返回值： 返回的是这一段反转后的头节点
2. 终止条件： 当剩余数量不够k时，终止循环，返回头节点
3. 处理： 对长度为k的链表进行反转（思路痛206题）

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 特殊情况处理
        if (k == 1) return head;
        // 终止条件
        ListNode tmp = head;
        int kk = k;
        while (k-- > 1 && tmp != null) {
            tmp = tmp.next;
        }
        if (tmp == null) {
            return head;
        }
        // 每一轮的翻转操作
        ListNode pre = head.next;
        tmp = head;
        k = kk;
        while (k-- > 1) {
            ListNode tmp2 = pre.next;
            pre.next = tmp;;
            tmp = pre;
            pre = tmp2;
        }
        head.next = reverseKGroup(pre, kk);

        // 返回值
        return tmp;
    }
}