理论

参考这篇
循环链表可以用来解决约瑟夫环问题。

思维导图

第一章 Introduce Dummy Node in Linked List

刷题第一站

LeetCode 203 移除链表元素

对于移除链表中等于目标值元素的思路非常简单：
找到目标元素，然后将该目标元素的上一个元素链接这个目标元素的下一个元素即可。
我们这里发现一个很重要的问题，我们需要记录当前元素的前一个元素，但是头节点是没有前驱的，因此如果我们设置一个Dummy Node，就省去了判断。

这样，对于任意一个待处理节点，其有两种可能：
1.是待删除元素，则将前一个指针指向当前节点下一个，然后改变当前节点
2.如果不是待删除元素，则直接更改当前节点

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        ListNode pre = dummyNode; // 待处理元素前面节点，这里待处理元素借用head变量
        while (head != null) { // 如果待处理元素不为空，就继续
            if (head.val == val) {
                pre.next = head.next;
            } else {
                pre = head;
            }
            head = head.next;
        }
        return dummyNode.next;
    }
}

LeetCode 83 删除排序链表中的重复元素

方法一：
一次遍历，对于当前元素cur，下一个元素的值和当前元素有两种情况
1.相等，则cur = cur.next.next; 此时当前元素不变
2.不相等，则cur = cur.next。即当前元素处理完毕
这样就由一个问题，每个待处理元素都要和下一个元素的值比较，因此当前元素不能使最后一个元素，即不能遍历整个链表。
这个方法保留的是重复元素中的第一个。

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return null;
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }
}

方法二：借助双指针保留重复元素第一个
略
方法三：哨兵节点+双指针保留重复元素中最后一个
略

LeetCode 82 删除排序链表中的重复元素 II

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return null;
        ListNode dummyNode = new ListNode(Integer.MIN_VALUE, head);
        ListNode cur = dummyNode; // 待处理节点
        while (cur != null && cur.next != null) {
            ListNode pre = cur;
            ListNode temp = cur.next;
            while ((temp != null && temp.val == pre.val) || (temp != null && temp.next != null && temp.val == temp.next.val)) {
                pre = temp;
                temp = temp.next;
            }
            cur.next = temp;
            cur = temp;
        }
        return dummyNode.next;
    }
}

以上是个人代码。下面写LeetCode官网的思路和代码

方法一：一次遍历
思路与算法

由于给定的链表是排好序的，因此重复的元素在链表中出现的位置是连续的，因此我们只需要对链表进行一次遍历，就可以删除重复的元素。由于链表的头节点可能会被删除，因此我们需要额外使用一个哑节点（dummy node）指向链表的头节点。

具体地，我们从指针 \textit{cur}cur 指向链表的哑节点，随后开始对链表进行遍历。如果当前 \textit{cur.next}cur.next 与 \textit{cur.next.next}cur.next.next 对应的元素相同，那么我们就需要将 \textit{cur.next}cur.next 以及所有后面拥有相同元素值的链表节点全部删除。我们记下这个元素值 xx，随后不断将 \textit{cur.next}cur.next 从链表中移除，直到 \textit{cur.next}cur.next 为空节点或者其元素值不等于 xx 为止。此时，我们将链表中所有元素值为 xx 的节点全部删除。

如果当前 \textit{cur.next}cur.next 与 \textit{cur.next.next}cur.next.next 对应的元素不相同，那么说明链表中只有一个元素值为 \textit{cur.next}cur.next 的节点，那么我们就可以将 \textit{cur}cur 指向 \textit{cur.next}cur.next。

当遍历完整个链表之后，我们返回链表的的哑节点的下一个节点 \textit{dummy.next}dummy.next 即可。

细节

需要注意 \textit{cur.next}cur.next 以及 \textit{cur.next.next}cur.next.next 可能为空节点，如果不加以判断，可能会产生运行错误。

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return null;
        ListNode dummyNode = new ListNode(Integer.MIN_VALUE, head);
        ListNode cur = dummyNode; // 待处理节点，待处理元素及之前都是已经好的
        while (cur.next != null && cur.next.next != null) { // 后续可能出现重复元素
            if (cur.next.val == cur.next.next.val) {
                int x= cur.next.val;
                while (cur.next != null && cur.next.val == x) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }

        return dummyNode.next;
    }
}

第二章 Basic skills in Linked List you should know

刷题第一站

LeetCode 707 设计链表

暂时略

876. 链表的中间结点

这道题非常普遍。但是很重要！

// 寻找中间元素，如果是偶数，定位第一个
class Solution {
    public ListNode middleNode(ListNode head) {
        if (head == null) return null;
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

解法一：

class Solution {
    public ListNode middleNode(ListNode head) {
        if (head == null) return null;
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next.next != null ? fast.next.next : fast.next;
        }
        return slow;
    }
}

解法二：这里不是两种解法，只是代码不一样而已。

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

第三章 Fast Slow Pointers

刷题第一站

LeetCode 141 环形链表

设置快慢指针；快指针走一步，慢指针走两步，如果相遇则有环。

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) return false;
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
}

LeetCode 142 环形链表 II

这个没什么玄妙的，记住即可。
设置快慢指针，快指针每次都两步，慢指针每次都一步；如果相遇，则认为有环
在有环情况下，慢指针回到原处，快指针在原位，然后快慢各走一步，相遇即环的入口。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) return null;
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }
        /*if (fast != slow) { // 无环  这个判断在某些例子中无法通过，如只有一个节点head = new ListNode(1)。
            return null;
        }*/
        if (fast.next == null || fast.next.next == null) { // 无环
            return null;
        }
        slow = head;
        while (fast != slow) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

160. 相交链表

这道题也不知道算不算是双指针，不过还是放在这里。当然细想一下其实也是算的。
这道题有很多做法，但是这个做法真实太妙了。
但是细想就会发现很简单很巧妙 A和B两个链表长度可能不同，但是A+B和B+A的长度是相同的，所以遍历A+B和遍历B+A一定是同时结束。如果A,B相交的话A和B有一段尾巴是相同的，所以两个遍历的指针一定会同时到达交点如果A,B不相交的话两个指针就会同时到达A+B（B+A）的尾节点！

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 特判
        if (headA == null || headB == null) {
            return null;
        }
        ListNode head1 = headA;
        ListNode head2 = headB;

        while (head1 != head2) {
            if (head1 != null) {
                head1 = head1.next;
            } else {
                head1 = headB;
            }

            if (head2 != null) {
                head2 = head2.next;
            } else {
                head2 = headA;
            }
        }
        return head1;
    }
}

java

第四章其它

刷题第一站反转链表

LeetCode 206 反转链表

class Solution {
    // 每一个节点，指向前面节点即可
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next; // 在改变指针前，记录当前节点的下一个
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

LeetCode 92 反转链表 II

这道题和LeetCoode 206 反转链表是相似的，但是这里放在了哨兵节点这一节。
因为这时候链表反转头节点可能会变化。
有人可能问反转链表头节点是一定会变化的呀。为什么不用dummyNode？体会一下，其实用也行，不用更简洁。
思路很简单！
定位到left的前一个，从left开始反转，当然要记录下第一个待反转节点。反转完。再将四个位置链接起来。

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(0, head);
        ListNode preNode = dummy;
        for (int i = 1; i < left; i++) {
            preNode = preNode.next;
        }
        ListNode cur = preNode.next; // 待反转的第一个链表，即left位置处
        ListNode first = cur; // 记录下第一个元素
        ListNode pre = null; // 待处理元素的前一个元素;
        for (int i = 0; i <= right - left; i++) { //要翻转链表的长度
                ListNode next = cur.next; // 记录下待反转元素的下一个，方便找到
                cur.next = pre;
                pre = cur;
                cur = next;
        }
        preNode.next = pre;
        first.next = cur;

        return dummy.next;
    }
}

25. K 个一组翻转链表

这个是抄LeetCode的答案，有空自己写一下。很简单。

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy; // pre是每一组待反转元素的前一个，head充当待反转元素的第一个

        while (head != null) {
            // 查看剩余部分长度是否大于等于K
            ListNode tail = pre;
            for (int i = 0; i < k; i++) {
                tail = tail.next;
                if (tail == null) {
                    return dummy.next;
                }
            }
            ListNode next = tail.next; // 记录下反转组后一个节点
            // 根据head和tail反转
            ListNode[] reverse = myReverse(head, tail);
            head = reverse[0];
            tail = reverse[1];
            // 把子链表重新接回原链表
            pre.next = head;
            tail.next = next;
            pre = tail;
            head = tail.next;
        }

        return dummy.next;
    }

    public ListNode[] myReverse(ListNode head, ListNode tail) {
        ListNode prev = tail.next;
        ListNode p = head;
        while (prev != tail) {
            ListNode next = p.next;
            p.next = prev;
            prev = p;
            p = next;
        }
        return new ListNode[] {tail, head};
    }
}

24. 两两交换链表中的节点

实话说，这一道和上一道一模一样。

 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy; // 每一组待交换节点的前一个
        ListNode cur = dummy.next; // 待处理节点第一个
        while (cur != null && cur.next != null) { // 如果处理的节点有两个
            // 其实就是分为反转；接和更换循环条件这三步
            ListNode first = cur;
            ListNode second = cur.next;
            ListNode next = second.next; // 反转组后面第一个
            pre.next = second;
            second.next = first;
            first.next = next;

            // 更换循环内容
            cur = next;
            pre = first;
        }
        return dummy.next;
    }
}

上面是我的代码，但官网的更加简洁，因此也写过来。哎，还是不如官网。
这里并没有记录那么多，也是因为这里反转短的原因。其实我们即使反转K个，也可以如此，无非是遍历一遍，但是就比较麻烦了。我上面的写法对更长的也是通用的。

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy; // 每一组待交换节点的前一个
        while (pre.next != null && pre.next.next != null) { // 如果处理的节点有两个
            ListNode first = pre.next;
            ListNode second = pre.next.next;

            pre.next = second;
            first.next = second.next;
            second.next = first;
            pre = first;
        }
        return dummy.next;
    }
}

刷题第二站链表归并排序

21. 合并两个有序链表

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        if (l1 == null) {
            cur.next = l2;
        }
        if (l2 == null) {
            cur.next = l1;
        }
        return dummy.next;
    }
}

148. 排序链表

「147. 对链表进行插入排序」要求使用插入排序的方法对链表进行排序，插入排序的时间复杂度是 O(n^2)O(n
2
)，其中 nn 是链表的长度。这道题考虑时间复杂度更低的排序算法。题目的进阶问题要求达到 O(n \log n)O(nlogn) 的时间复杂度和 O(1)O(1) 的空间复杂度，时间复杂度是 O(n \log n)O(nlogn) 的排序算法包括归并排序、堆排序和快速排序（快速排序的最差时间复杂度是 O(n^2)O(n
2
)），其中最适合链表的排序算法是归并排序。

方法
归并排序基于分治算法。最容易想到的实现方式是自顶向下的递归实现，考虑到递归调用的栈空间，自顶向下归并排序的空间复杂度是 O(\log n)O(logn)。如果要达到 O(1)O(1) 的空间复杂度，则需要使用自底向上的实现方式。

找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 22 步，慢指针每次移动 11 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。

对两个子链表分别排序。

class Solution {
    // 将一个链表排序，返回头节点
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode next = slow.next;
        slow.next = null;
        ListNode node1 = sortList(head);
        ListNode node2 = sortList(next);
        return mergeTwoLists(node1, node2);
    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        if (l1 == null) {
            cur.next = l2;
        }
        if (l2 == null) {
            cur.next = l1;
        }
        return dummy.next;
    }
}

147. 对链表进行插入排序

// 对于数组而言的插排，是对于每个待定元素，从后向前在排好序的元素中查找
 // 但是单链表是不能逆序的，因此要顺着找。
class Solution {
    // 节点可能变化，因此用dummyNode
    public ListNode insertionSortList(ListNode head) {
        if (head == null) return head;
        ListNode dummy = new ListNode(Integer.MIN_VALUE, head);
        ListNode pre = head; // 待处理元素前面一个，方便判断当前元素是否需要处理,第一个已经排好序
        ListNode cur = head.next; // 待处理元素，该元素前面的都已排序
        while (cur != null) {
            if (cur.val >= pre.val) {
                pre = pre.next;
            } else { // 此时就需要插入了,需要找到待插入位置的前一个，即第一个≤的位置
                ListNode temp = dummy;
                while (temp.next.val <= cur.val) {
                    temp = temp.next;
                }
                pre.next = cur.next;
                cur.next = temp.next;
                temp.next = cur;
            }
            cur = pre.next;
        }
        return dummy.next;
    }
}

23. 合并K个升序链表

思路1：合并k个升序链表，我们已知合并两个有序链表。一次先拿两个合并，之后再拿下一个合并即可。
代码略。
思路2：借用优先队列，就小根堆。每次将K个链表首元素放入，获取最小值为当前节点；如此下去即可。
代码略。
思路3：分治算法，和归并排序思路一样。

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }
    private ListNode merge(ListNode[] lists, int left, int right) {
        if (left == right) return lists[left];
        if (left > right) return null; // 比如本题测试例子为[]时
        int mid = left + ((right - left) >> 1);
        ListNode head1 = merge(lists, left, mid);
        ListNode head2 = merge(lists, mid + 1, right);
        return mergeTwoLists(head1, head2);
    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 方法体略，上面有
    }
}

109. 有序链表转换二叉搜索树

这道题有很多解法，由于第一种采用的分治，因此放在这里。
解法一：分治

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return new TreeNode(head.val);
        // 找到链表的中间节点作为平衡二叉树搜索树的根节点

        // ListNode slow = head, fast = head;
        // 下面这个代码，如果链表长度是偶数，则slow来到中间的前一个，如果设置pre的话
        /*while (fast.next != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }*/
        ListNode slow = head, fast = head, pre = null;
        while (fast.next != null) {
            fast = fast.next.next != null ? fast.next.next : fast.next;
            pre = slow;
            slow = slow.next;
        }

        // 生成当前子树的根节点
        TreeNode root = new TreeNode(slow.val);
        // 拆分左右链表
        pre.next = null;
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(slow.next);
        return root;
    }
}

解法二：递归+中序遍历优化
说实话没懂
这道题还有一个类似题目是LeetCode 109 有序链表转换二叉搜索时.做法一模一样。

刷题第三站两数之和

2. 两数相加

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int carry = 0;
        ListNode head = null, tail = null;
        while (l1 != null || l2 != null) {
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1 + n2 + carry;
            if (head == null) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        if (carry > 0) {
            tail.next = new ListNode(carry);
        }
        return head;
    }
}

445. 两数相加 II

这道题其实没什么要说的
方法一：链表逆序，然后按照上面的方式解决，时间复杂度是O(n)，空间复杂度是O(1)。
方法二：借助栈，自然空间复杂度就是O(n)了。
这里用法一解：

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return reverseList(addTwoNumbersInLists(reverseList(l1), reverseList(l2)));
    }

    private ListNode reverseList(ListNode head) {
        ListNode pre = null, cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    private ListNode addTwoNumbersInLists(ListNode l1, ListNode l2) {
        int carry = 0;
        ListNode head = null, tail = null;
        while (l1 != null || l2 != null) {
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1 + n2 + carry;
            if (head == null) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        if (carry != 0) {
            tail.next = new ListNode(carry);
        }
        return head;
    }
}

刷题第四站其它

86. 分隔链表

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode smallHead = new ListNode(0);
        ListNode smallTail = smallHead;
        ListNode largerhead = new ListNode(0);
        ListNode largerTail = largerhead;
        while (head != null) {
            if (head.val < x) {
                smallTail.next = new ListNode(head.val);
                smallTail = smallTail.next;
            } else {
                largerTail.next = new ListNode(head.val);
                largerTail = largerTail.next;
            }
            head = head.next;
        }
        smallTail.next = largerhead.next;
        return smallHead.next;
    }
}

725. 分隔链表

解题思路很简单，懒得写了做这些题是为了锻代码能力
法一：创建新的节点

class Solution {
    public ListNode[] splitListToParts(ListNode root, int k) {
        int N = 0;
        ListNode cur = root;
        while (cur != null) {
            cur = cur.next;
            N++;
        }
        int width = N / k, rem = N % k;

        ListNode[] ans = new ListNode[k];
        cur = root;
        for (int i = 0; i < k; i++) {
            ListNode head = new ListNode(0), write = head;
            for (int j = 0; j < width + (i < rem ? 1 : 0); j++) {
                if (cur != null) {
                    write = write.next = new ListNode(cur.val);
                    cur = cur.next;
                }
            }
            ans[i] = head.next;
        }

        return ans;
    }
}

解法二：截短原有链表

class Solution {
    public ListNode[] splitListToParts(ListNode root, int k) {
        int N = 0;
        ListNode cur = root;
        while (cur != null) {
            cur = cur.next;
            N++;
        }

        int width = N / k, rem = N % k;
        ListNode[] res = new ListNode[k];
        cur = root;
        for (int i = 0; i < k; i++) {
            ListNode head = cur;
            for (int j = 0; j < width + (i < rem ? 1 : 0) - 1; j++) {
                if (cur != null) cur = cur.next;
            }
            if (cur != null) {
                ListNode prev = cur;
                cur = cur.next;
                prev.next = null;
            }
            res[i] = head;
        }
        return res;
    }
}

61. 旋转链表

这道题很简单：定位到待截取的前一个元素，然后链接即可，我这里就不写代码了。但是LeetCode的答案是将整个链表合成一个圆，这各思路以后可能用上，因此这里就用LeetCode官网的思路解题了。解法可看官网。

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null) {
            return null;
        }

        int N = 1;
        ListNode cur = head;
        while (cur.next != null) { // 这里的计数方法诶什么和上一题不一样，目的是让cur最终指向链表最后一个元素
            cur = cur.next;
            N++;
        }
        cur.next = head; // 成环
        int n = N - k % N; // 计算从哪里开始拆开，即这各节点后面指向null
        while (n-- > 0) { // 寻找都断开点
            cur = cur.next;
        }
        ListNode res = cur.next;
        cur.next = null;
        return res;
    }
}

328. 奇偶链表

odd奇，even偶
这道题LeetCode官网的代码很简洁，但我懒得看了，没有必要。

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null) return null;
        ListNode jiTail = null; // 奇元素就放在其后面
        ListNode ouHead = null;
        ListNode ouTail = null; // 偶元素放在它后面
        int index = 1;
        ListNode cur = head;
        while (cur != null) {
            if (index % 2 == 1) { // 奇数
                if (jiTail == null) {
                    jiTail = cur;
                } else {
                    jiTail = jiTail.next = cur;
                }
            } else { // 偶数
                if (ouTail == null) {
                    ouHead = ouTail = cur;
                } else {
                    ouTail = ouTail.next = cur;
                }
            }
            cur = cur.next;
            index++;
        }
        jiTail.next = ouHead;
        if (ouTail != null) ouTail.next = null;
        return head;
    }
}

143. 重排链表

找到中间节点；逆序后半部分；两个链表合并

class Solution {
    public void reorderList(ListNode head) {
        // 找到链表中间节点，偶数则定位前一个
        if (head == null) return;
        ListNode mid = middleNode(head);
        ListNode head2 = mid.next;
        mid.next = null;
        head2 = reverseList(head2);
        mergeTwoLists(head, head2);
    }
    private ListNode middleNode(ListNode head) {
        if (head == null) return null;
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    private ListNode reverseList(ListNode head) {
        ListNode pre = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    // l1的长度要么等于l2，要么比其大1
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummyNode = new ListNode(0);
        ListNode cur = dummyNode;
        while(l1 != null && l2 != null) {
            cur = cur.next = l1;
            l1 = l1.next;
            cur = cur.next = l2;
            l2 = l2.next;
        }
        if (l1 != null) cur.next = l1;
        return dummyNode.next;
    }
}

1669. 合并两个链表

没啥说的，练练手！

class Solution {
    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        ListNode dummyNode = new ListNode(0, list1);
        // 寻找到a-1和b+1位置的节点
        int index = -1;
        ListNode cur = dummyNode;
        while (index != a - 1) {
            cur = cur.next;
            index++;
        }
        ListNode pre = cur;
        while(index != b + 1) {
            cur = cur.next;
            index++;
        }
        ListNode next = cur;
        if (list2 == null) {
            pre.next = next;
            return dummyNode.next;
        }
        pre.next = list2;
        while(list2.next != null) {
            list2 = list2.next;
        }
        list2.next = next;
        return dummyNode.next;
    }
}

138. 复制带随机指针的链表

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        Node cur = head;
        while (cur != null) {
            Node copy = new Node(cur.val);
            copy.next = cur.next;
            cur.next = copy;
            cur = copy.next;
        }
        cur = head;
        while (cur != null) {
            Node next = cur.next;
            next.random = cur.random == null ? null : cur.random.next;
            cur = cur.next.next;
        }

        Node oldHead = head;
        Node newHead = head.next;
        Node res = newHead;
        while (oldHead != null) {
            oldHead.next = newHead.next;
            newHead.next = newHead.next == null ? null : newHead.next.next;
            oldHead = oldHead.next;
            newHead = newHead.next;
        }
        return res;
    }
}

234. 回文链表

整个流程可以分为以下五个步骤：

找到前半部分链表的尾节点。
反转后半部分链表。
判断是否回文。
恢复链表。
返回结果。
执行步骤一，我们可以计算链表节点的数量，然后遍历链表找到前半部分的尾节点。

我们也可以使用快慢指针在一次遍历中找到：慢指针一次走一步，快指针一次走两步，快慢指针同时出发。当快指针移动到链表的末尾时，慢指针恰好到链表的中间。通过慢指针将链表分为两部分。

若链表有奇数个节点，则中间的节点应该看作是前半部分。

步骤二可以使用「206. 反转链表」问题中的解决方法来反转链表的后半部分。

步骤三比较两个部分的值，当后半部分到达末尾则比较完成，可以忽略计数情况中的中间节点。

步骤四与步骤二使用的函数相同，再反转一次恢复链表本身。

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }

        // 找到前半部分链表的尾节点并反转后半部分链表
        ListNode firstHalfEnd = endOfFirstHalf(head);
        ListNode secondHalfStart = reverseList(firstHalfEnd.next);

        // 判断是否回文
        ListNode p1 = head;
        ListNode p2 = secondHalfStart;
        boolean result = true;
        while (result && p2 != null) {
            if (p1.val != p2.val) {
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }        

        // 还原链表并返回结果
        firstHalfEnd.next = reverseList(secondHalfStart);
        return result;
    }

    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    private ListNode endOfFirstHalf(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

1290. 二进制链表转整数

这道题大家可能觉得，哇，好简单啊！但是你写出来的代码真的这么简单吗？这么清晰吗？

class Solution {
    public int getDecimalValue(ListNode head) {
        int res = 0;
        while (head != null) {
            res = (res << 1) + head.val;
            head = head.next;
        }
        return res;
    }
}

dd

LeetCode 237 删除链表中的节点

class Solution {
    public void deleteNode(ListNode node) {
       while (node.next != null && node.next.next != null) { // 只要不是倒数第二个元素，将下一位值copy
            node.val = node.next.val;
            node = node.next;
       }
       // 此时node.next != null 但node.next.next == null
       node.val = node.next.val;
       node.next = null;
    }
}

官网的解法更是：

public void deleteNode(ListNode node) {
    node.val = node.next.val;
    node.next = node.next.next;
}

总结

链表的种类主要为：单链表，双链表，循环链表
链表的存储方式：链表的节点在内存中是分散存储的，通过指针连在一起。
链表是如何进行增删改查的。
数组和链表在不同场景下的性能分析。

链表

理论

思维导图

第一章 Introduce Dummy Node in Linked List

刷题第一站

第二章 Basic skills in Linked List you should know

刷题第一站

第三章 Fast Slow Pointers

刷题第一站

第四章 其它

刷题第一站 反转链表

刷题第二站 链表归并排序

刷题第三站 两数之和

刷题第四站 其它

dd

总结

第四章其它

刷题第一站反转链表

刷题第二站链表归并排序

刷题第三站两数之和

刷题第四站其它