二刷力扣--链表

链表

链表类型：
单链表（可以访问后面的一个节点）
双链表（可以访问前后节点）
循环链表（最后一个节点指向首节点）

在Python中定义单链表节点：

class ListNode:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next
1
2
3
4

移除链表元素 203.

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

为了统一处理删除操作，在head节点前添加一个哑节点。

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        pre = dummy
        cur = dummy.next
        while cur:
            if cur.val == val:
                pre.next = cur.next 
                cur = cur.next
            else:
                pre = pre.next
                cur = cur.next
        
        return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14

Python有垃圾回收，不需要手动删除节点。

设计链表 707.

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

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

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

class MyLinkedList:
    def __init__(self):
        self.dummy = Node(-1, None)
        self.max_index = -1  

    def get(self, index: int) -> int:
        if index < 0 or index > self.max_index:
            return -1
        cur = self.dummy.next 
        for  i in range(index):
            cur = cur.next
        return cur.val

    def addAtHead(self, val: int) -> None:
        self.dummy.next  = Node(val, self.dummy.next)
        self.max_index += 1

    def addAtTail(self, val: int) -> None:
        cur = self.dummy
        while cur.next:
            cur = cur.next
        cur.next = Node(val)
        self.max_index += 1

    def addAtIndex(self, index: int, val: int) -> None:
        if  index < 0 or index > self.max_index + 1:
            return 
        cur = self.dummy
        i = 0
        for i in range(index):
            cur = cur.next

        cur.next = Node(val, cur.next)
        self.max_index += 1

    def deleteAtIndex(self, index: int) -> None:
        if  index < 0 or index > self.max_index:
            return 
        cur = self.dummy
        for i in range(index):
            cur = cur.next

        cur.next = cur.next.next 
        self.max_index -= 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

反转链表 206.

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

使用temp保存cur.next ，因为反转后cur.next就改变了，无法再访问原来的下一个元素了。

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
      pre = None
      cur = head
      while cur:
        temp = cur.next # 下一个节点
        cur.next  = pre # 反转next方向

        pre = cur
        cur = temp # 去下一个
      
      return pre 
1
2
3
4
5
6
7
8
9
10
11
12

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

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

有些题解里很多cur.next.next.next，看起来很麻烦。 用临时节点记录一下似乎就不用那么多next了。而且也不用考虑.next赋值的顺序了。

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        cur = dummy
        # 交换cur后面的两个节点
        while cur.next and cur.next.next:
            node1 = cur.next        
            node2 = node1.next  
            node3 = node2.next  
            #  cur->node1->node2-->node3(node2.next)  ----> cur->node2->node1-->node3(node2.next)  
            cur.next = node2  
            node2.next = node1 
            node1.next = node3
           
            cur = node1 
        
        return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

删除链表的倒数第N个节点 19.

#双指针 #哑节点
双指针的应用。快指针fast先走n步，当快指针到达倒数第1个节点时，慢指针slow到达倒数n+1个节点，删除slow的下一个节点。
哑节点对简化删除操作很有用，如果不用哑节点，删除head就要特殊处理。

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        fast = dummy
        slow = dummy
        # 当fast 到达倒数第1个节点， slow到达倒数第n+1个节点
        for i in range(n):
            fast = fast.next
        while fast.next :
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next 
        return dummy.next 
1
2
3
4
5
6
7
8
9
10
11
12
13

链表相交 面试题 02.07. 同 160

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

两个链表如果有相同的节点，则从相同节点开始，一直到末尾都是相同的。
让较长的链表先走 abs(lengthA-lengthB)个节点，然后比较两个链表。

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        def getLength(head):
            length = 0
            while head:
                head = head.next
                length += 1
            return length
        lengthA = getLength(headA)
        lengthB = getLength(headB) 
        Long, Short = (headA, headB) if lengthA > lengthB  else (headB, headA)

        for _ in range (abs(lengthA- lengthB)):
            Long = Long.next
        while Short:
            if Short == Long:
                return Short
            else:
                Short = Short.next
                Long = Long.next
        return None
      
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

环形链表II 142.

#集合 #双指针

1. 直接用set记录访问过的节点，再次遇到则表明出现了环。

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        visited = set()
        pos = head
        while pos:
            if  pos in visited:
                return pos
            else:
                visited.add(pos)
            pos = pos.next
        return None
1
2
3
4
5
6
7
8
9
10
11

2. 双指针。快指针fast一次走两步，慢指针slow一次走一步。如果有环，两个指针一定会遇到。
   而找到环的入口比较难，需要推导一下。（这个不太好理解，推荐看代码随想录的视频）
   

相遇时，slow指针走过的节点数是 x+y, fast走过的节点数是 x+y+ n(y+z) ,n>=1
fast一次走两个节点，所以走过的节点数是slow的两倍，即 x+y+n(y+z) = 2（x+y)。 化简一下，得到 x = (n-1)(y+z) + z
n = 1时， x = z 也就是说，一个指针index1从slow与fast相遇点出发，一个指针index2从头节点出发，会在入口节点相遇。

n大于1时和n为1的时候 效果是一样的，一样可以通过这个方法找到 环形的入口节点，只不过，index1 指针在环里 多转了(n-1)圈，然后再遇到index2，相遇点依然是环形的入口节点

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast = head
        slow = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            if slow == fast:
                index1 = fast
                index2 = head
                while index1 != index2:
                    index1 = index1.next
                    index2 = index2.next
                return index2
        
        return None
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

链表小结

哑节点对简化链表操作很有用。添加一个哑节点，对头节点的处理会和其他节点一样。
双指针是常用的方法，可以用来判断链表是否有环，找到链表倒数第n个元素。