Okii's blog

仅作为记录自己的学习过程

0%

Leetcode 链表篇

发表于 分类于
本文字数： 6.8k 阅读时长 ≈ 12 分钟

Leetcode刷题记录——链表篇

Leetcode203 移除链表

如果对于一个链表，头节点的操作和其他节点的操作需要2个逻辑的话，建立一个虚拟头节点往往会大大降低难度

Python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 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]:
        dummy_head = ListNode(next = 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

Leetcode707 设计链表

特定位置插入删除的操作，要考虑好头尾结点的特殊情况就行

Python代码如下：

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
50
51
52
53
54
55
56
57
58
59
60
61
62
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = None

class MyLinkedList:

    def __init__(self):
        self.dummy_node = ListNode()
        self.size = 0


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

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

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

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

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return
        current = self.dummy_node
        for i 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)

Leetcoe206 反转链表

首先定义一个current指针，指向头结点，pre指向None

从头开始反转时，需要先定义一个temp指针保留current.next

接着将current.next指向pre，再移动pre到current的位置，current再移到temp的位置

这是一次反转的操作

只要当前current非空，就可以一直进行

最后返回的pre就是头节点

Python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Definition for singly-linked list.
# 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]:
        pre = None
        current = head
        while current:
            temp = current.next
            current.next = pre
            pre = current
            current = temp
        return pre

Leetcode24 两两交换链表中的节点

卡了好久没找出错误，思维只定在了第一轮，还得是gpt

问题在于你每次交换节点时，都将 dummy_node.next 指向了当前的 temp 节点，这样会导致 dummy_node.next 不断指向链表中的同一个节点，而不是每次都更新。在进行两两交换时，dummy_node.next 应该指向新的头节点，而不是固定地指向 temp。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 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_node = ListNode(next=head)
        cur = head
        while cur and cur.next:
            # next_node = cur.next
            temp = cur.next
            next_head = cur.next.next
            dummy_node.next = temp
            temp.next = cur
            cur.next = next_head
            cur= next_head
        return dummy_node.next

画图模拟过程就行

Python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 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_node = ListNode(next=head)
        cur = dummy_node
        while cur.next and cur.next.next:
            next_head = cur.next.next.next
            temp = cur.next
            cur.next = temp.next
            cur.next.next = temp
            temp.next = next_head
            cur = cur.next.next
        return dummy_node.next

另有递归的写法，留到下次再回来做的时候想

Leetcode19 删除链表的倒数第n个节点

双指针的经典应用

如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。

删掉slow.next所指向的节点就可以了。

Python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 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]:
        dummy_node = ListNode(next=head)
        # 创建两个指针，慢指针和快指针，并将它们初始化为虚拟节点
        fast = dummy_node
        slow = dummy_node
        # 快指针比慢指针快 n 步
        for i in range(n):
            fast = fast.next
        # 当快指针走到链表尾节点时,slow刚好在要删除的那个节点的前一个节点,slow.next = slow.next.next就可以达到删除的目的了
        while fast.next:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return dummy_node.next

Leetcode160 链表相交

两链表若相交，则相交之后的长度是相同的，相交前的长度不同

首先遍历两链表，分别求出它们的长度lenA， lenB

再求出它们的长度差dif，先让长的那个链表移动dif步，则两链表就在同一起跑线了

接着遍历到尾节点的同时判断curA == curB

Python代码如下：

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
# 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]:
        lenA = 0 
        lenB = 0
        curA = headA
        curB = headB
        while curA:
            curA = curA.next
            lenA += 1
        while curB:
            curB = curB.next
            lenB += 1
        curA = headA
        curB = headB
        if lenA > lenB:
            dif = lenA -lenB
            for i in range(dif):
                curA = curA.next
        else:
            dif = lenB - lenA
            for i in range(dif):
                curB = curB.next
        while curA:
            if curA == curB:
                return curA
            else:
                curA = curA.next
                curB = curB.next
        return None

Leetcode142 环形链表Ⅱ

  • 首先判断链表中是否有环

定义slow、fast指针，首先指向head

slow一次移动一步，fast一次移动两步

若链表有环，fast一定比slow先进环

等到slow和fast都进环后，由于fast比slow每次多移动一步，并且在环内，这就变成了一个追及问题

也就是说，不论这个环多大，fast总能追上slow

  • 然后需要找到环的入口

假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点再到环形入口节点节点数为 z

相遇时： slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针， （y+z）为 一圈内节点的个数A

因为fast指针是一步走两个节点，slow指针一步走一个节点， 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2：

(x + y) * 2 = x + y + n (y + z)

两边消掉一个（x+y）: x + y = n (y + z)

因为要找环形的入口，那么要求的是x，因为x表示头结点到 环形入口节点的的距离

所以要求x ，将x单独放在左面：x = n (y + z) - y

再从n(y+z)中提出一个（y+z）来，整理公式之后为如下公式：x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针

这个公式说明什么呢？

先拿n为1的情况来举例，意味着fast指针在环形里转了一圈之后，就遇到了slow指针了。

当 n为1的时候，公式就化解为 x = z，

这就意味着，从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。

也就是在相遇节点处，定义一个指针index1，在头结点处定一个指针index2

让index1和index2同时移动，每次移动一个节点， 那么他们相遇的地方就是 环形入口的节点

Python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 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]:
        slow = head
        fast = head
        # 为什么不写 while fast.next and fast.next.next
        # 会出现头结点为[]时, 会报错Nonetype has attribute next, null没有next了
        # ps:而且判断条件是按顺序来的, 写在前面的先判断, 如果前面错了就不往后判断了
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                slow = head
                while slow != fast:
                    slow = slow.next
                    fast = fast.next
                return slow
        return None

Leetcode82 删除链表中的重复元素Ⅱ

当cur指向的节点值与cur.next指向的节点值相同时

就让cur不断向后移动，直到cur指向的节点值与cur.next指向的节点值不相同时，停止移动

此时，判断pre.next是否等于cur，如果相等，说明pre与cur之间没有重复节点，就让pre移动到cur的位置否则，说明pre与cur 之间有重复节点，我们就让pre.next指向cur.next

然后让cur继续向后移动

继续上述操作，直到 cur为空，遍历结束

最后返回dummy_node.next

Python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy_node = pre = ListNode(0, head)
        cur = head
        while cur:
            while cur.next and cur.next.val == cur.val:
                cur = cur.next
            if pre.next == cur:
                pre = cur
            else:
                pre.next = cur.next
            cur = cur.next
        return dummy_node.next