leetcode刷题-链表总结（python）

一、链表基础

1.链表定义

链表是一系列节点组成的元素集合。每个节点包含两个部分，数据域item和指向下一个节点的指针next。通过节点之间的互相连接最终串成一个链表。

单链表，链表的入口节点称为头结点head，最后一个节点指向None。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

双链表，双链表的每个节点有两个指针，一个指向前一个一个指向后一个节点。

class ListNode:
    def __init__(self, val=0, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next

循环链表，链表首尾相连

 2.链表的插入和删除

插入，时间复杂度O(1)

p.next = curNode.next
curNode.next = p

 删除，时间复杂度O(1)

curNode.next = curNode.next.next

二、移除链表元素

力扣题目链接

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

删除头节点和删除中间的节点操作不一样 ，为了统一方便操作，可以引入虚拟头结点。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        # 设置一个虚拟头结点，避免单独讨论头结点是val的情况
        dummy_head = ListNode(next = head)
        current = dummy_head   # current和dummy_head都指向同一个链表结构
        while current.next:    # 在这个循环的过程中修改的该链表结构
            if current.next.val == val:
                current.next = current.next.next
            else:
                current = current.next
        return dummy_head.next    # 最后返回这个是因为current已经向后移动了，但dummy_head还是指向的该被修改后的链表结构

三、设计链表

力扣题目链接

设置虚拟头结点，方便操作，虚拟头结点下标可以认为是-1。每次查询插入删减要记得做判断。下面给出用单链表的做法。

class ListNode:
    def __init__(self, val = 0, next = None):
        self.val = val
        self.next = next

class MyLinkedList:

    def __init__(self):
        self.dummy_head = ListNode()  # 创建一个虚拟头结点，虚拟头结点永远是虚拟头结点，其下标认为是-1
        self.size = 0     # 目前的长度是0

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1
        current = self.dummy_head
        for _ in range(index):
            current = current.next
        return current.next.val

    def addAtHead(self, val: int) -> None:
        self.dummy_head.next = ListNode(val, self.dummy_head.next)
        self.size += 1

    def addAtTail(self, val: int) -> None:
        current = self.dummy_head
        while current.next:
            current = current.next
        current.next = ListNode(val)
        self.size += 1

    def addAtIndex(self, index: int, val: int) -> None:
        if index > self.size or index < 0:
            return
        else:
            current = self.dummy_head
            for _ in range(index):
                current = current.next
            current.next = ListNode(val,current.next)
            self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return
        else:
            current = self.dummy_head
            for _ in range(index):
                current = current.next
            current.next = current.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)

四、反转链表

力扣题目链接

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

 设置一个cur指针，一个pre指针。持续向后移动实现链表反转。

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        pre = None    # 反转之后头结点前面得有一个None
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre 

五、两两交换链表中的节点

力扣题目链接 

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

使用虚拟头结点，两两交换的每一次分为三个步骤，持续循环就行。

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy_head = ListNode(0,head)
        cur = dummy_head
        while cur.next and cur.next.next:   # 这里就考虑了是奇数的情况了
            tmp = cur.next
            cur.next = cur.next.next
            tmp1 = cur.next.next
            cur.next.next = tmp
            tmp.next = tmp1
            cur = cur.next.next
        return dummy_head.next

六、删除链表的倒数第N个结点

力扣题目链接 

 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

 快慢指针，虚拟头结点。快指针先移动n+1个单位，然后快慢指针一起移动直到快指针指到None，因为快慢指针的相对位置永远不变，所以快指针指到None的时候，慢指针恰好指到倒数第N个结点的前一个节点（不指向该节点是为了删除方便）。

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # 双指针法（快慢指针），fast先移动n步，然后fast，slow同时移动直到fast指向None，这时slow指向倒数第n个节点
        # 为了方便删除，期望slow指向n的前一个节点，所以fast可以先移动n+1步，再进行同时移动
        dummy_head = ListNode(0,head)
        fast = dummy_head
        slow = dummy_head
        for _ in range(n+1):
            fast = fast.next
        while fast:
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next
        return dummy_head.next

七、链表相交

力扣题目链接

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

图示两个链表在节点 c1 开始相交：

分别求出A和B的长度，让长的那个指针移动到和短的对齐，这样两个一起向后走，遇到相同的节点就证明存在交点。

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        # 注意是指针相同，不是值相同
        lenA = 0
        lenB = 0
        # 求链表A的长度
        cur = headA
        while cur:
            lenA += 1
            cur = cur.next
        # 求链表B的长度
        cur = headB
        while cur:
            lenB += 1
            cur = cur.next
        # 求出长度差，让长的那个往后移动长度差个单位
        # 固定B是长的，A是短的可以减少代码量
        curA = headA
        curB = headB
        if lenA > lenB:
            curA, curB = curB, curA
            lenA, lenB = lenB, lenA    # 固定B是长的那个
        delta = lenB - lenA
        for _ in range(delta):      #对齐了AB的指针
            curB = curB.next
        # A,B同时往后移动，发现相同的指针就停下来返回
        while curA:
            if curA == curB:
                return curB
            else:
                curA = curA.next
                curB = curB.next
        return None

 八、环形链表

力扣题目链接

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

使用快慢指针方法，快指针每次移动两个，慢指针每次移动一个。如果存在环，则快慢指针一定会在环内相遇。为什么是在慢指针走第一圈的过程就肯定会相遇呢？可以自己随便画一个环形图，指定一个环入口位置也就是慢指针的位置，让快指针在任意位置开始追赶慢指针，不管快指针从哪开始，在慢指针走的一圈之内最后一定是下图这样的效果。两个指针再各自走一步就会相遇

判断完一定会相遇后就要判断环的入口在哪，可以看下面的图。

相遇的时候慢指针走了x+y，快指针走了x+y+n(y+z) ，由于快指针的速度是慢指针的二倍，所以

2(x+y)=x+y+n(y+z)，消掉x+y，可以得到x+y=n(y+z)，x=n(y+z)-y，x=(n-1)(y+z)+z

假设n=1，也就是x等于z，当两个点相遇后让让一个指针指向头结点，一个在相遇的节点，开始向后走，相遇的时候就是环形入口节点。

同理n>1，两个新的指针始终会在入口节点相遇。

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


class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast = head
        slow = head
        while fast and fast.next:   # 判断fast.next是为了怕列表没有环，但循环中fast要next.next，这样会出现错误
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                slow = head
                while fast != slow:
                    fast = fast.next
                    slow = slow.next
                return slow
        return None

作者：A_小果子