算法工程师的日常
0%

链表

发表于 更新于 分类于 ，

单链表

总结基础操作

反转后保留head和尾部

1
2
3
4
5
6
7
8
9
def reversePart(head):
    pre = None
    cur = head
    while cur:
        next = cur.next
        cur.next = pre
        pre = cur
        cur = next
    return pre【新的头】, head【新的尾】

输入head后，返回反转后的头pre和尾head

涉及指定位置的反转

对于206和24两道题，其实本质上要处理的还是两个点，也就是node0和node1,因此都定义两个点就够了，只是在处理的过程中，需要借用到一些临时的变量，这时候，可以使用一些node2等作为辅助。

双指针技巧

1
2
3
4
5
slow = head
fast = head
while fast and fast.nex:
    slow = slow.next
    fast = fast.next.next

统计链表长度

1
2
3
4
5
cnt = 0
cur = head
while cur:
    cnt += 1
    cur = cur.next

虚拟头

方便后续对指针的操作，在删除链表元素以及去除重复项中都有用。可以看到基本上对单链表中翻转或者元素操作的地方，都用到了dummy这个虚拟的链表节点，方便对一些异常节点的处理。就是第一个节点一旦不太好定义或者后面会随着代码中的处理逻辑会发生变化，比如删除指定元素万一删除到了自己，或者旋转链表的时候头也变了，这些情况下用一个虚拟的头接着后面的head然后处理完之后再用next进行获取就好。

先dummy=ListNode(-1)后一定不能直接对dummy操作，也就是不能直接dummy=dummy.next，那样随着后面写代码的话，dummy的head就不知道哪里去了，应该先定义一个cur=dummy，然后访问的时候使用cur=cur.next来按照顺序访问指针，最后我们获取整个更新后的链表的时候，直接使用dummy.next就好了。

使用到dummy基本上都要left=dummy=ListNode(None,next=…),然后用left操作，最后返回dummy.next就可以

操作的先后顺序

在链表中，主要是对指针进行操作，那么操作的顺序，以及如何使用next，使用的时机要把握好，不然容易出现cur=cur.next后，再把指针指向cur，因为这时cur都变了，你再指的话是有问题的，所有对于具体的问题要画出图来分析，我们结合两个案例来说明，第一是链表的翻转

1
2
3
4
5
while cur:
    next = cur.next
    cur.next = pre
    pre = cur
    cur = next

这里相当于前面的None和节点1，变成了后面迭代中节点1和节点2，但是呢，我们得先把节点2的指针存下来，不然后面cur.next变了之后，你就再也访问不到了。

还有一些案例，比如合并有序链表，其实这个相当于重新构建一个链表，我们写的时候不太需要保存后面的指针了，因为不需要像翻转链表那样，不保存的话会导致里面的值被修改掉。这个案例的代码就很简单如下：

1
2
3
while cur:
    cur.next = head1
    cur = head1

就是先指完后再重置cur到移动指针的位置。

重新定义个链表

1
2
3
4
5
6
dummy = ListNode(-1)
cur = dummy # 面说到了，我们定义了dummy后，还需要定义一个cur指向他，对他的值进行修改，然后cur动dummy不动
for i in res[::-1]:
    cur.next = ListNode(i)
    cur = cur.next
return dummy.next

注意，千万不能写成如下的形式

1
2
3
4
5
dummy = ListNode(-1)
for i in res[::-1]:
    dummy.next = ListNode(i)
    dummy = dummy.next
return dummy.next

这里用到dummy指针就有用了

将链表从中间断开

目的是为了二分，便于后面进行归并排序，下面这段代码集中了错误和正确的，可以对比下

1
2
3
4
5
6
7
8
9
# 错误的
slow = cur
fast = cur
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
right = slow.next
slow.next = None
left_sort_results = merge_sort(cur)

这样在递归的时候，程序会无限，无法跳出，下面看下没问题的结果

1
2
3
4
5
6
7
8
9
slow = cur
fast = cur
pre = None
while fast and fast.next:
    pre = slow
    slow = slow.next
    fast = fast.next.next
pre.next = None
left_sort_results = merge_sort(cur)

关于步进访问

这里需要指出的是，使用

1
2
while fast:
	fast = fast.next

这里这么做是没问题的，但是如果一旦涉及到fast.next=xxx的时候就要注意了，可能会改变这个链表原来的数据流的走向，建议画图看奇偶链表。

关于链表重新整理顺序

我们看到很多对链表进行操作，排序也好，还是交换顺序也好，对于翻转，这种是有规律的，而且是反向操作，因此有固定的模版可以写的，对于一些其它稀奇古怪的题，可以尝试如下的做法

1
2
3
4
5
6
7
small_dummy = ListNode(-1)
big_dummy = ListNode(-2)

small = small_dummy
big = big_dummy

# 然后遍历cur，把数值放到，small和big的next中

就是用两个虚拟的指针来操作，然后进行组合，如 分隔链表[86]，奇偶链表[328]，合并链表等操作，简单连接就是借助外部的指针来对现有的指针进行串起来。

多指针同时操作链表存在的问题

对于单个指针，使用cur=cur.next可以步进访问链表的元素，使用cur.next=cur.next.next也可是进行断点连接某节点。但是对于多个指针，如两个指针，同时操作链表，则会存在一个指针修改了链表的结构，另一个再修改的话会出问题的情况，如奇偶链表那道题，和其它的很多题都不一样，它有两个指针指着链表，然后都需要进行链表值的替换等，这样一个链表修改了值，另外一个链表再访问就会出问题。

快慢指针操作

1
2
3
4
5
6
7
8
9
10
11
12
# 1. 建议写法
slow = head
fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
# 2. 不建议写法
slow = head
fast = head.next
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

翻转系列

反转链表[206]

题号为 206， 位于 https://leetcode.cn/problems/reverse-linked-list/
题解如下

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]:
        node0 = None
        node1 = head
        while node1:
            node2 = node1.next
            node1.next = node0
            node0 = node1
            node1 = node2
        return node0

总结下来，就是先保存好数据，代码是

node2 = node1.next

然后操作

node1.next = node0

然后平移

node0 = node1
node1 = node2

相当于从[1,2,3,4,5]中的1,2为node0,node1,变成了2为node1,3为node2

递归方法如下：

1
2
3
4
5
6
7
8
9
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        def recur(cur, pre):
            if not cur: return pre     # 终止条件
            res = recur(cur.next, cur) # 递归后继节点
            cur.next = pre             # 修改节点引用指向
            return res                 # 返回反转链表的头节点
        
        return recur(head, None)       # 调用递归并返回

来自 https://leetcode.cn/problems/reverse-linked-list/solutions/2361282/206-fan-zhuan-lian-biao-shuang-zhi-zhen-r1jel/

建议用下面的递归，更加的简答，但是不太好懂，我在代码中添加了注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 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]:
        if head==None or head.next==None:
            return head
        ret = self.reverseList(head.next)
        # 假设的是head.next后面已经反转好了，假设head=1,head.next.next就是5 4 3 2 的2， 然后2 的next=1,然后1再指定下
        head.next.next = head
        head.next = None
        return ret

反转链表 II[92]

位于 https://leetcode.cn/problems/reverse-linked-list-ii/
题解如下：

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head, left, right):
        dummy = ListNode(-1, next=head)
        first = dummy
        for i in range(left-1):
            first = first.next
        first_above = first
        first = first.next

        second = dummy
        for j in range(right):
            second = second.next
        second_after = second.next

        cur = first
        second.next = None

        def reversePart(head):
            pre = None
            cur = head
            while cur:
                next = cur.next
                cur.next = pre
                pre = cur
                cur = next
            return pre, head
        
        reverse_head, reverse_tail = reversePart(cur)
        first_above.next = reverse_head
        reverse_tail.next = second_after
        return dummy.next

两两交换链表中的节点[24]

题号 24， 位于 https://leetcode.cn/problems/swap-nodes-in-pairs/description/
题解如下：

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]:
        node0 = dummy = ListNode(next=head)
        node1 = head
        while node1 and node1.next:
            node2 = node1.next
            node3 = node2.next

            node0.next = node2
            node2.next = node1
            node1.next = node3

            node0 = node1
            node1 = node3
        return dummy.next

和上面一样的分析思路，先保存好数据，然后操作，然后平移，这个过程可以看 https://leetcode.cn/problems/swap-nodes-in-pairs/solutions/2374872/tu-jie-die-dai-di-gui-yi-zhang-tu-miao-d-51ap/

递归解法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
# 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==None or head.next==None:
            return head
        next = head.next
        head.next = self.swapPairs(next.next)
        next.next = head
        return next

和前面的那道题不太一样，这里不需要pre那个东西的

K 个一组翻转链表[25]

位于 https://leetcode.cn/problems/reverse-nodes-in-k-group/description/
题解如下：

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
class Solution:
    def reverseKGroup(self, head, k):
        # 旋转链表
        def reversePart(head):
            pre = None
            cur = head
            while cur:
                next = cur.next
                cur.next = pre
                pre = cur
                cur = next
            return pre, head
        # 统计节点数量
        node1 = head
        cnt = 0
        while node1:
            cnt += 1
            node1 = node1.next
        # 保存每段的链表反转后的开始点和结束点
        res = []
        cur = head
        old_cur = head
        for i in range(cnt // k): # 这里不要考虑最后一段哈，最后一段在res.append([cur, cur])这里
            for j in range(k - 1):
                cur = cur.next
            tail_old = cur.next
            cur.next = None
            new_head, new_tail = reversePart(old_cur)
            res.append([new_head, new_tail])
            cur = tail_old
            old_cur = tail_old
        res.append([cur, cur])
        for i in range(len(res) - 1):
            res[i][1].next = res[i + 1][0]
        return res[0][0]

旋转链表[61]

位于 https://leetcode.cn/problems/rotate-list/description/
思路是先闭合为环，然后再打断
题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # 统计长度
        cur = head
        cnt = 0
        while cur:
            cnt = cnt + 1
            cur = cur.next
        # 表示成环
        cur2 = head
        while cur2.next:
            cur2 = cur2.next
        cur2.next = head
        # 断点
        diff = cnt - k%cnt
        cur3 = head
        for i in range(diff-1):
            cur3 = cur3.next
        new_head = cur3.next
        cur3.next = None
        return new_head

排序链表 [148]

位于 https://leetcode.cn/problems/sort-list
使用冒泡排序来做的话，比较耗时，做法如下，建议将图画出来，便于理解中间的指针的操作

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
class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        dummy = ListNode(-1, next=head)
        cnt = 0
        cur = head
        while cur:
            cnt += 1
            cur = cur.next
        for i in range(cnt):
            node0 = dummy # 注意这里
            node1 = dummy.next
            while node1 and node1.next:
                if node1.val <= node1.next.val:
                    node0 = node0.next
                    node1 = node1.next
                else:
                    node2 = node1.next
                    node3 = node2.next
                    node0.next = node2
                    node2.next = node1
                    node1.next = node3

                    node0 = node2
                    node1 = node1

        return dummy.next

上述代码中我们使用了node0和node1两个指针来做维护的，当然在程序的执行过程中，我们还使用了其他的临时指针，这些在程序运行过程中定义就好了，不需要在进入while的之前定义，这道题和上面的24有点像，它也是定义了node0和node1，然后其他的需要的时候自己定义，具体操作看具体情况。

可以使用归并排序算法来做，具体的思路如下，这是我自己写的，也遇到了很多的问题，主要的问题在代码中已经说明了

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
class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        def merge(p1, p2):
            dummy = ListNode(-1)
            cur = dummy
            while p1 and p2:
                if p1.val < p2.val:
                    cur.next = p1
                    p1 = p1.next
                else:
                    cur.next = p2
                    p2 = p2.next
                cur = cur.next
            cur.next = p1 if p1 else p2
            return dummy.next

        def merge_sort(cur):
            if not cur or not cur.next:
                return cur
            slow = cur
            fast = cur
            pre = None
            while fast and fast.next: # 这里要注意为啥要用pre这个东西，如果不要，直接将slow.next作为后半段，然后将cur作为前半段的话，会出问题
                pre = slow
                slow = slow.next
                fast = fast.next.next
            pre.next = None
            left_sort_results = merge_sort(cur)
            right_sort_results = merge_sort(slow)
            return merge(left_sort_results, right_sort_results)
        return merge_sort(head)

重排链表[143]

位于 https://leetcode.cn/problems/reorder-list/description/
思路：将链表全部断开，变成一个一个的

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
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        from collections import deque
        cur = head
        node_list = []
        while cur:
            node_list.append(cur)
            cur = cur.next
        
        queue = deque([])
        for i in node_list[::-1]:
            i.next = None
            queue.insert(0, i)

        dummy = ListNode(-1)
        cur = dummy
        while queue:
            if queue:
                cur.next = queue.popleft()
                cur = cur.next
            if queue:
                cur.next = queue.pop()
                cur = cur.next
        return dummy.next

删除系列

删除链表的倒数第 N 个结点[19]

题号 19，位于 https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/
题解如下：

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, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        vals = []
        dummy = head
        while dummy:
            vals.append(dummy.val)
            dummy = dummy.next
        t = len(vals) - n + 1
        dummy2 = ListNode(-1, next=head)
        dummy3 = dummy2
        cnt = 0
        while dummy2:
            cnt = cnt + 1
            if cnt == t:
                dummy2.next = dummy2.next.next
                return dummy3.next
            dummy2 = dummy2.next
        return dummy2.next

这种做法也可以，不过比较耗时，接下来的方法比较简答，思路也很容易理解，就是先让fast移动k位，然后快慢指针同时移动，代码如下：

1
2
3
4
5
6
7
8
9
10
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        slow = fast = dummy = ListNode(-1,next=head) # 一步到位劝赋值
        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

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

位于 https://leetcode.cn/problems/remove-duplicates-from-sorted-list/description/
题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        left = dummy = ListNode(-9999,next=head)
        right = head # 最好别right=dummy，和后面那道题保持一致
        while right:
            if right.val == left.val:
                right = right.next
                continue
            left.next = right
            left = left.next
            right = right.next
        left.next = None
        return dummy.next

和之前的删除数组元素中的重复值很像，代码如下：

1
2
3
4
5
6
7
8
9
10
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        left = 0
        for right in range(1, len(nums)):
            pass #这里不需要操作啥
            if nums[right] == nums[left]:
                continue
            left = left + 1    
            nums[left] = nums[right]
        return left + 1

只是一个用while的，一个用for，链表这里没法用for,用while的话要手动给right移动一位才可以。

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

位于 https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        values = set()
        duplicated_values = set()
        while cur:
            val = cur.val
            if val in values:
                duplicated_values.add(val)
            values.add(val)
            cur = cur.next
        
        left = dummy = ListNode(-9999,next=head)
        right = head # 最好别right=dummy，和后面那道题保持一致
        while right:
            if right.val in duplicated_values:
                right = right.next
                continue
            left.next = right
            left = left.next
            right = right.next
        left.next = None
        return dummy.next

移除链表元素[203]

位于 https://leetcode.cn/problems/remove-linked-list-elements/description/
题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        if not head:
            return head
        left = dummy = ListNode(-1, next=head)
        right = head # 不能right=dummy，不然会一直while
        while right:
            if right.val == val:
                right = right.next
                continue
            left.next = right
            left = left.next  # 这两段代码不要顺序弄错了
            right = right.next
        left.next = None
        return dummy.next

最好用一个dummy来做，这样方便操作。和数组中的删除一个元素很像，那道题的代码如下：

1
2
3
4
5
6
7
8
9
10
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        left = 0
        for right in range(len(nums)):
            pass #这里不需要操作啥
            if nums[right] == val:
                continue
            nums[left] = nums[right]
            left = left + 1
        return left

只是一个用while的，一个用for，链表这里没法用for,用while的话要手动给right移动一位才可以。

相交-环等问题

相交链表[160]

题号 160， 位于 https://leetcode.cn/problems/intersection-of-two-linked-lists/
解法如下

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
# 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]:
        #遍历到A的尾部
        head1 = headA
        while head1.next:
            head1 = head1.next
        
        #遍历到B的尾部
        head2 = headB
        while head2.next:
            head2 = head2.next

        # 首位相连构成环
        head1.next = headB
        # 快慢指针
        slow = headA
        fast = headA
        while fast and fast.next:
            slow = slow.next # 这里容易弄错，把判断写在前面了
            fast = fast.next.next
            if slow == fast:
                p = headA
                q = slow
                while p != q:
                    p = p.next
                    q = q.next
                head1.next = None
                head2.next = None
                return p

        head1.next = None
        head2.next = None
        return None

更简单的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
# 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) -> ListNode:
        A, B = headA, headB 
        while A != B: #这里写错成A and B
            A = A.next if A else headB
            B = B.next if B else headA
        return A

环形链表[141]

位于 https://leetcode.cn/problems/linked-list-cycle/

代码如下：

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, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
            return False
        slow = head
        fast = head # 这里也可以head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next # 别写错了
            if slow == fast:
                return True
        return False

环形链表II[142]

位于 https://leetcode.cn/problems/linked-list-cycle-ii/description/
题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 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 and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast: # 注意：下面的操作不熟悉
                p = slow 
                q = head
                while p!=q:
                    p= p.next
                    q=q.next
                return p
        return None

分割系列

分隔链表[725]

代码如下：

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
class Solution:
    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:
        cur = head
        cnt = 0
        while cur:
            cnt = cnt + 1
            cur = cur.next
        a, b = divmod(cnt, k)
        res = [a for i in range(k)]
        for i in range(b):
            res[i] = res[i] + 1
        
        new_res = []
        cur = head
        for lens in res:
            if lens==0:
                new_res.append(None)
                continue
            else:
                new_res.append(cur)
            for i in range(lens-1): #注意点1
                cur = cur.next
            new_head = cur.next
            cur.next = None # 注意点2
            cur = new_head
        return new_res

分隔链表[86]

位于：https://leetcode.cn/problems/partition-list/description/
解法如下

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
# Definition for singly-linked list.
# 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]:
        small_dummy = ListNode(-1)
        big_dummy = ListNode(-2)

        small = small_dummy
        big = big_dummy

        cur = head
        while cur:
            if cur.val < x:
                small.next = cur
                small = small.next
            else:
                big.next = cur
                big = big.next
            cur = cur.next
        big.next = None
        small.next = big_dummy.next
        return small_dummy.next

上述我在写的时候没有注意，直接用如下代码，导致了错误

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        small = ListNode(-1)
        big = ListNode(-2)
        
        cur = head
        while cur:
            if cur.val < x:
                small.next = cur
                small = small.next
            else:
                big.next = cur
                big = big.next
            cur = cur.next
        big.next = None
        small.next = big.next
        return small.next

可以看到，到最后的话，small都不知道是啥了，因此还是需要使用一个指针，来指向dummy 也就是这里的small和big 小细节要注意

定位系列

训练计划 II[LCR 140]

位于：https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof

题解如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def trainingPlan(self, head: Optional[ListNode], cnt: int) -> Optional[ListNode]:
        lens = 0
        cur = head
        while cur:
            lens += 1
            cur = cur.next
        p = head
        for i in range(lens-cnt):
            p = p.next
        return p

链表的中间结点[876]

位于 https://leetcode.cn/problems/middle-of-the-linked-list
这么做也挺方便的，不用便利两次，就是多了些存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 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: ListNode) -> ListNode:
        if head.next == None:
            return head
        cur = head
        allNodes = []
        while cur.next:
            allNodes.append(cur)
            cur = cur.next
        allNodes.append(cur)
        return allNodes[int(len(allNodes)//2)]

LRU 缓存[146]

位于 https://leetcode.cn/problems/lru-cache/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class LRUCache(collections.OrderedDict):

    def __init__(self, capacity: int):
        super().__init__()
        self.capacity = capacity


    def get(self, key: int) -> int:
        if key not in self:
            return -1
        self.move_to_end(key)
        return self[key]

    def put(self, key: int, value: int) -> None:
        if key in self:
            self.move_to_end(key)
        self[key] = value
        if len(self) > self.capacity:
            self.popitem(last=False)

在get

双链表

链表合并

合并两个有序链表[21]

位于 https://leetcode.cn/problems/merge-two-sorted-lists/description/
题解如下：

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
# Definition for singly-linked list.
# 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]:
        if not list1 and not list2:
            return None
        if not list1:
            return list2
        if not list2:
            return list1
        dummy = ListNode(-1, next=list1)
        cur = dummy #上面说到了，我们定义了dummy后，还需要定义一个cur指向他，对他的值进行修改，然后cur动dummy不动
        head1 = list1
        head2 = list2
        while head1 and head2:
            if head1.val <= head2.val:
                cur.next = head1
                head1 = head1.next
            else:
                cur.next = head2
                head2 = head2.next
            cur = cur.next
        cur.next = head1 if head1 else head2
        return dummy.next

合并 K 个升序链表[23]

位于：https://leetcode.cn/problems/merge-k-sorted-lists
题目虽然为困难，但是思路很简答，就是把上面那个题改为递归就好

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        def mergeSingle(list1, list2):
            if not list1 and not list2:
                return None
            if not list1:
                return list2
            if not list2:
                return list1
            dummy = ListNode(-1, next=list1)

            cur = dummy
            head1 = list1
            head2 = list2
            while head1 and head2:
                if head1.val <= head2.val:
                    cur.next = head1
                    cur = head1
                    head1 = head1.next
                else:
                    cur.next = head2
                    cur = head2
                    head2 = head2.next
            cur.next = head1 if head1 else head2
            return dummy.next
        if len(lists)==0: # 注意边界
            return None
        if len(lists)==1: # 注意边界
            if not lists[0]: # 注意边界
                return None
            return lists[0] # 注意边界
        if len(lists)==2:
            return mergeSingle(lists[0], lists[1])
        return mergeSingle(lists[0], self.mergeKLists(lists[1:]))

奇偶链表[328]

位于 https://leetcode.cn/problems/odd-even-linked-list/description/
题解如下：

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
# Definition for singly-linked list.
# 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 not head:
            return head
        if not head.next:
            return head
        A = head
        B = head.next

        first = A
        second = B

        while second and second.next:
            temp1 = first.next.next
            first.next = first.next.next
            first = temp1

            temp2 = second.next.next
            second.next = second.next.next
            second = temp2

        first.next = B
        return A

容易写错为如下：

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
# Definition for singly-linked list.
# 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 not head:
            return head
        if not head.next:
            return head
        A = head
        B = head.next

        first = A
        second = B
        
        # 下面这么写的话自己画画图就知道一旦使用fast.next后，链表原来的顺序结构就被打断了，再去寻的话就会出错。
        while first and first.next:
            temp1 = first.next.next
            first.next = first.next.next
            first = temp1

        while second and second.next:
            temp2 = second.next.next
            second.next = second.next.next
            second = temp2

        first.next = B
        return A

两数相加

两数相加[2]

位于 https://leetcode.cn/problems/add-two-numbers
代码如下：

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        def get_list(head):
            cur = head
            res = []
            while cur:
                res.append(cur.val)
                cur = cur.next
            return res
        l1_res = get_list(l1)
        l2_res = get_list(l2)

        max_lens = max(len(l1_res), len(l2_res))
        res = []
        a = 0
        for i in range(max_lens):
            n1 = l1_res[i] if i<len(l1_res) else 0
            n2 = l2_res[i] if i<len(l2_res) else 0
            a, b = divmod(n1+n2+a, 10)
            res.append(b)
        if a>0:
            res.append(a)
        dummy = ListNode(-1) #说到了，我们定义了dummy后，还需要定义一个cur指向他，对他的值进行修改，然后cur动dummy不动
        cur = dummy
        for i in res:
            cur.next = ListNode(i)
            cur = cur.next
        return dummy.next

和下面的这道题一样，没啥好说的

两数相加 II[445]

位于 https://leetcode.cn/problems/add-two-numbers-ii

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, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # 获取链表的值
        def get_list(head):
            cur = head
            res = []
            while cur:
                res.append(cur.val)
                cur = cur.next
            return res
        l1_res = get_list(l1)[::-1]
        l2_res = get_list(l2)[::-1]

        # 获取最大的长度
        max_lens = max(len(l1_res), len(l2_res))
        res = []
        a = 0
        for i in range(max_lens):
            n1 = l1_res[i] if i<len(l1_res) else 0
            n2 = l2_res[i] if i<len(l2_res) else 0
            a, b = divmod(n1+n2+a, 10)
            res.append(b)
        if a>0:
            res.append(a)
        dummy = ListNode(-1) # 说到了，我们定义了dummy后，还需要定义一个cur指向他，对他的值进行修改，然后cur动dummy不动
        cur = dummy
        for i in res[::-1]:
            cur.next = ListNode(i)
            cur = cur.next
        return dummy.next