最近通过leetcode刷题复习链表相关的知识，将其划分为三大部分，分别是链表基础操作、进阶技巧、综合题型。

一、链表基础操作

1，哨兵节点

哨兵节点及在链表的头节点之前创建一个无值，指向头节点的虚拟节点，作为新的操作节点，该操作可以避免诸如前驱节点判断、头节点操作、空链表处理时的分类讨论。

例题1：leetcode707：设计链表

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

分析：该题需要笔者设计一个链表的类，满足增删改查的核心功能，由此我们需要注意，当头节点为空时会出现分类讨论的情况，但使用虚拟头节点可以很好的避免讨论这一点。与此同时，使用size记录链表大小也可以很好的来判断当前下标是否越界。

from typing import Optional
class ListNode:
    def __init__(self,val):
        self.val=val
        self.next=None

class MyLinkedList:

    def __init__(self):
        self.head=ListNode(0)
        self.size=0
    def get(self, index: int) -> int:
        if index<0 or index>=self.size:
            return -1
        head=self.head
        for i in range(index+1):
            head=head.next
        return head.val
    def addAtHead(self, val: int) -> None:
        Node=ListNode(val)
        head=self.head
        Node.next=head.next
        head.next=Node
        self.size+=1
    def addAtTail(self, val: int) -> None:
        Node=ListNode(val)
        head=self.head
        while head.next:
            head=head.next
        head.next=Node
        self.size+=1
    def addAtIndex(self, index: int, val: int) -> None:
        if index<0 or index>self.size:
            return 
        Node=ListNode(val)
        head=self.head
        for i in range (index):
            head=head.next
        Node.next=head.next
        head.next=Node
        self.size+=1
    def deleteAtIndex(self, index: int) -> None:
        if index<0 or index>=self.size:
            return 
        head=self.head
        for i in range(index):
            head=head.next
        head.next=head.next.next
        self.size-=1
# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)

2，链表的中间节点

链表的中间节点，可以用快慢指针的形式快速找到

例题2：leetcode876：链表的中间节点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

from typing import Optional
# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head==None:
            return None
        fast=slow=head
        while fast and fast.next!=None:
            fast=fast.next.next
            slow=slow.next
        return slow
"""
值得注意的是，当slow=head.next而fast=head时，slow最后指向的是偏右的中间节点。
上述得到的是偏左的中间节点
"""

3,翻转链表

例题3：leetcodeLCR024：翻转链表

翻转链表可以用两种方法来写，第一种是迭代，第二种则是分治法，两周方法都非常经典，也有必要掌握，同时翻转链表也是后续诸多复杂操作的基础。

方法一：迭代法

# Definition for singly-linked list.
from typing import Optional
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head
        pre=None
        cur=head
        while cur:
            temp=cur.next
            cur.next=pre
            pre=cur
            cur=temp
        return pre

迭代法重在pre与cur指针的相互赋值，值得注意的是，pre初始为None，cur初始为head，这样可以一直遍历为pre为新的头节点，而cur为None

方法二：分支法

# Definition for singly-linked list.
from typing import Optional
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head
        new_head= self.reverseList(head.next)
        head.next.next=head
        head.next=None
        return new_head

4,求得链表的倒数第N个节点

例题4：leetcode19：删除链表的倒数第N个节点

链表的倒是第N个节点可以用起始点不同的指针去求得，注意不是快慢指针而是起始点不同的指针，只需要让前一个指针比后一个指针恒定快N步，那么当前一个指针指向尾节点时，后一个指针就是倒数第N个节点。

from typing import Optional
# Definition for singly-linked list.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        fast=head
        slow=head
        for i in range(n):
            fast=fast.next
        if fast==None:
            return head.next
        while fast.next:
            fast=fast.next
            slow=slow.next
        slow.next=slow.next.next
        return head

if __name__ == '__main__':
    head = ListNode(1)
    head.next = ListNode(2)
    head.next.next = ListNode(3)
    head.next.next.next = ListNode(4)
    head.next.next.next.next = ListNode(5)
    n = 2
    s = Solution()
    s.removeNthFromEnd(head, n)

5，链表的分割处理操作

例题5：leetcode328：奇偶链表

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别分组，保持它们原有的相对顺序，然后把偶数索引节点分组连接到奇数索引节点分组之后，返回重新排序的链表。

第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。

请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。

你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

题目要求将链表以奇偶的形式进行分割，此时如果将链表视为一个链表，会导致非常复杂的双指针操作，但是如果视为两个链表一个负责穿奇数，一个负责穿偶数，最后将两个链表连起来，那么题目将会简单一个层次。

# Definition for singly-linked list.
from typing import Optional
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head==None:
            return None
        odd=head
        even=head.next
        even_head=even
        while even and even.next:
            odd.next=even.next
            odd=odd.next
            even.next=odd.next
            even=even.next
        odd.next=even_head
        return head

二、链表进阶操作

1，分割链表

只需明白将一个链表视为两个链表并分别穿插即可。

例题1：leetcode86：分隔链表

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。同时，为了避免分类讨论，一定要使用虚拟头节点。

from typing import Optional
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        lower_head=ListNode(0)
        higher_head=ListNode(0)
        
        lower=lower_head
        higher=higher_head
        
        p=head
        
        while p:
            if p.val<x:
                lower.next=p
                lower=lower.next
            else:
                higher.next=p
                higher=higher.next
            p=p.next
        higher.next=None
        
        lower.next=higher_head.next
        
        return lower_head.next

2，旋转链表

所谓旋转链表，就是将链表像数组一样右循环或者左循环偏移，与数组需要reverse不同的是，链表只需要找到倒数的N节点以及使用头节点即可。

例题2：leetcode61：旋转链表

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

首先将k%len，得到真正需要右移的位数，随后使用寻找倒数第N个节点的方法来得到关键节点，最后穿插即可。

# Definition for singly-linked list.
from typing import Optional
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def get_len(self,head:Optional[ListNode])->int:
        len=0
        cur=head
        while cur!=None:
            len+=1
            cur=cur.next
        return len

    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if head==None:
            return None
        dis=k%self.get_len(head)
        if dis==0:
            return head
        pre=cur=head
        for i in range(dis):
            cur=cur.next
        while cur.next:
            cur=cur.next
            pre=pre.next

        rotate_head=pre.next
        pre.next=None
        cur.next=head
        return rotate_head

值得注意的是，特殊情况，当dis==0，以及head==None时，都需要进行特殊处理，否则程序会报错。

3，相交链表

例题3：leetcode160：相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

此题需要配合链表循环的特性去寻找，分析如下：

从headA与headB谁先到最后节点，就将其重置为另一个的头节点，这样，当相遇时就会刚刚好到第一个公共节点。

from typing import Optional
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        if not headA or not headB:
            return None
        p1=headA
        p2=headB
        while p1!=p2:
            p1=p1.next if p1 else headB   #这里必须使用p1,而不是p1.next，否则会无限循环
            p2=p2.next if p2 else headA   #只有这样当没有交点时，才会都指向null，从而退出
        return p1

4，合并两个有序链表

例题4：leetcode21：合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

首先，涉及到构建链表，首选虚拟头节点，随后，采用双指针分别遍历两个链表即可。

# Definition for singly-linked list.
from typing import Optional
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        head=dummy=ListNode()
        p1=list1
        p2=list2
        while p1 and p2:
            if p1.val<p2.val:
                dummy.next=p1
                p1=p1.next
            else:
                dummy.next=p2
                p2=p2.next
            dummy=dummy.next
        if p1:
            dummy.next=p1
        elif p2:
            dummy.next=p2
        return head.next

5,排序链表

例题5：leetcode148：排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

链表的数据结构，非常非常适合进行归并排序，首先使用二分法（找中点）来进行切割，随后使用合并两个有序链表的技巧来进行merge，可以非常非常方便地实现归并排序。

from typing import Optional
# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        slow,fast=head,head.next
        while fast and fast.next:
            fast=fast.next.next
            slow=slow.next
        mid=slow.next
        slow.next=None
        left=self.sortList(head)
        mid=self.sortList(mid)
        dummy=new_head=ListNode()
        while left and mid:
            if left.val<mid.val:
                dummy.next=left
                left=left.next
            else:
                dummy.next=mid
                mid=mid.next
            dummy=dummy.next
        dummy.next=left or mid
        return new_head.next

if __name__ == '__main__':
    s=Solution()
    list1=ListNode(1)
    list1.next=ListNode(2)
    list1.next.next=ListNode(4)
    list2=ListNode(1)
    list2.next=ListNode(3)
    list2.next.next=ListNode(4)
    print(s.sortList(list1))

值得注意的时，当使用归并排序时，一定要确保两个部分是断开的，否则会出现爆栈的情况，一定要注意。

6，两两交换链表中的节点

例题6：leetcode：24两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

这种题目就是纯粹的链表双指针操作，单个循环流程即为先将2指向1，随后1指向3，更新指针1的为3，指针2的为4，一直重复值指针1指向空为止。

from typing import Optional
# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head
        dummy=ListNode(0)  #虚拟头节点避免分类讨论
        dummy.next=head
        pre=dummy
        while head and head.next:
            first=head  #第一个节点
            second=head.next  #第二个节点
            pre.next=second  #前一个节点的next指向第二个节点
            first.next=second.next  #第一个节点的next指向第二个节点的next
            second.next=first  #第二个节点的next指向第一个节点
            pre=first  #前一个节点指向第一个节点
            head=first.next  #头节点指向第一个节点的next

        return dummy.next

这道题的关键是创建一个虚拟头节点去存储前一个节点，以便后续链接，否则会出现链接混乱。

三、链表综合操作

这部分的题型常常用到前面这些基础题的操作相混合，想要写好这类题型必须有十分扎实的基础。

1,重排链表

例题1：leetcode143：重排链表

此题综合了找中点、翻转链表、合并两个链表、虚拟头节点这四个操作，综合性质十足。

from typing import Optional
# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def reverse_list(self,head):
        pre=None
        cur=head
        while cur:
            temp=cur.next
            cur.next=pre
            pre=cur
            cur=temp
        return pre
    def find_mid(self,head):
        """
        得到偏左的节点，方便断开两段链表
        :param head:
        :return:
        """
        if not head:
            return head
        fast=head.next
        slow=head
        while fast and fast.next:
            slow=slow.next
            fast=fast.next.next
        return slow

    def reorderList(self, head: Optional[ListNode]) -> None:
        if not head or not head.next:
            return head
        pre_mid=self.find_mid(head)
        mid=pre_mid.next
        pre_mid.next=None #断开链表

        second_list=self.reverse_list(mid)
        first_list=head

        new_head=dummy_head=ListNode()   #虚拟头节点，以简化合并逻辑

        while second_list and first_list:
            dummy_head.next=first_list
            dummy_head=dummy_head.next
            first_list=first_list.next

            dummy_head.next=second_list                          
            dummy_head=dummy_head.next
            second_list=second_list.next                             #处理剩余节点，实际只有可能前一段剩余，
        dummy_head.next=second_list if second_list else first_list   # 但是为了少动点脑子就这样吧

        return new_head.next

2，两数相加

例题2：leetcode445：两数相加Ⅱ

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

本题综合了链表翻转以及链表加和这两个操作、关于链表加和，必须是倒序的各个数字才能模拟相加的过程。

# Definition for singly-linked list.
from typing import Optional
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def reverse_list(self,head: Optional[ListNode]) -> Optional[ListNode]:
        pre=None
        cur=head
        while cur:
            temp=cur.next
            cur.next=pre
            pre=cur
            cur=temp
        return pre
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        list1_head=self.reverse_list(l1)
        list2_head=self.reverse_list(l2)
        carry=0
        res=new_head=ListNode(0)
        while list1_head or list2_head or carry:       #注意，此处边界判断可以说是两数相加的精髓
            num1=list1_head.val if list1_head else 0   #使用该边界条件判断可以避免几乎所有的分类讨论
            num2=list2_head.val if list2_head else 0
            total=num1+num2+carry
            carry=total//10                            #注意此处需要整除，否则会出现小数
            num=total%10
            new_head.next=ListNode(num)
            new_head=new_head.next

            if list1_head:
                list1_head=list1_head.next
            if list2_head:
                list2_head=list2_head.next

        return self.reverse_list(res.next)

3，有环链表

例题3：leetcode141：环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head:
            return False
        slow=head
        fast=head
        while fast and fast.next:
            slow=slow.next
            fast=fast.next.next
            if slow==fast:
                return True
        return False

上述只是基本操作，即利用快慢指针，如果链表有环那么两个指针是一定会相遇的。接下来才是重头戏。

例题4：leetcode142：环形链表Ⅱ

给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

class Solution(object):
    def detectCycle(self, head):
        fast, slow = head, head
        while True:
            if not (fast and fast.next): return
            fast, slow = fast.next.next, slow.next
            if fast == slow: break
        fast = head
        while fast != slow:
            fast, slow = fast.next, slow.next
        return fast