算法刷题（二） - 链表操作

发表于 | 阅读次数：

反转链表

双指针，其中cur指向当前遍历节点，另一个prev指向当前节点的前一个节点，另外需要一个临时变量temp记录后一个节点，三个节点的指向交换即可。注意循环中的赋值顺序不能调换，先用临时变量记录后节点，再调转当前节点的指向，然后依次将prev、cur向后移动。 

1
2
3
4
5
6
7
8
9
10
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        cur = head
        while cur:
            temp = cur.next           
            cur.next = prev
            prev = cur
            cur = temp
        return prev

删除链表的节点

与反转链表相似的思路解决，更简单。注意特殊情况，删除头节点时直接返回head.next，以及删除节点后可直接退出循环。 

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        if head.val == val:
            return head.next
        prev, cur = None, head
        while cur:
            if cur.val == val:
                prev.next = cur.next
                break
            prev = cur
            cur = cur.next
        return head

拓展到链表中倒数第 k 个节点，仍然使用双指针。对链表遍历的终止条件是cur指向None，此时prev需在倒数第 k 个节点，则两个指针间相距 k 个节点。因此，先将cur单独向后移动 k 次，然后同时将两个指针向后遍历即可。 

1
2
3
4
5
6
7
8
9
class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        prev, cur = head, head
        for i in range(k):
            cur = cur.next
        while cur:
            cur = cur.next
            prev = prev.next
        return prev

复制复杂链表

这一题的难点在于，构造新链表的每个节点时，无法处理random的指向，因为指向的节点可能还未创建，没什么思路。题解给出的一个直观的方法是使用哈希表，先遍历一遍链表，将旧节点与创建的新节点一一对应起来，在第二次遍历中给新节点的指向赋值。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        dic = dict()
        cur = head
        if not head:
            return None
        while cur:
            node = Node(cur.val)
            dic[cur] = node
            cur = cur.next
        cur = head
        while cur:
            dic[cur].next = dic.get(cur.next)
            dic[cur].random = dic.get(cur.random)
            cur = cur.next
        return dic[head]

合并两个有序链表

用递归比较简单，思路也清晰，但是做的时候每次都想不到。 

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:

        if not l1:
            return l2
        elif not l2:
            return l1
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

自己写的迭代版本，用了额外空间，对比双指针指向的 l1 和 l2 的当前节点，当其中一个链表遍历结束后，将另一个链表的后续节点全部接入cur中。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = ListNode()
        cur = head
        if not l1:
            return l2
        if not l2:
            return l1
        while l1 and l2:
            if l1.val < l2.val:
                cur.val = l1.val
                l1 = l1.next
            else:
                cur.val = l2.val
                l2 = l2.next
            cur.next = ListNode()
            cur = cur.next
        if not l1:
            cur.val = l2.val
            cur.next = l2.next
        if not l2:
            cur.val = l1.val
            cur.next = l1.next
        return head

链表的第一个公共节点

一开始就明白肯定要用双指针，但一直没有想到怎么确定两个指针会相遇，只能用哈希表来存节点，空间复杂度做不到 O(1)。题解巧妙的地方在于，两个指针分别从两个链表开始遍历，遍历结束后再从另一个链表开始遍历，这样就平衡了长短链表的长度差，指针会正好在公共节点相遇。 

1
2
3
4
5
6
7
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        a, b = headA, headB
        while a != b:
            a = headB if not a else a.next
            b = headA if not b else b.next 
        return a