链表

基本技能

链表相关的核心点

null/nil 异常处理
dummy node 哑巴节点
快慢指针
插入一个节点到排序链表
从一个链表中移除一个节点
翻转链表
合并两个链表
找到链表的中间节点

常见题型

remove-duplicates-from-sorted-list

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        
        if head is None:
            return head
        
        current = head
        
        while current.next is not None:
            if current.next.val == current.val:
                current.next = current.next.next
            else:
                current = current.next
        
        return head

# 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: ListNode) -> ListNode:
        start = head
        while head:
            while head.next and head.val == head.next.val:
                head.next = head.next.next
            head = head.next
        return start

remove-duplicates-from-sorted-list-ii

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中没有重复出现的数字。

思路：链表头结点可能被删除，所以用 dummy node 辅助删除

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        
        if head is None:
            return head
        
        dummy = ListNode(next=head)
        
        current, peek = dummy, head
        find_dup = False
        while peek.next is not None:
            if peek.next.val == peek.val:
                find_dup = True
                peek.next = peek.next.next
            else:
                if find_dup:
                    find_dup = False
                    current.next = current.next.next
                else:
                    current = current.next
                peek = peek.next
        
        if find_dup:
            current.next = current.next.next
        
        return dummy.next

注意点 • A->B->C 删除 B，A.next = C • 删除用一个 Dummy Node 节点辅助（允许头节点可变） • 访问 X.next 、X.value 一定要保证 X != nil

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        dummy = ListNode(0, head)
        pre = dummy
        while head:
            cur = head.val
            if head.next and cur == head.next.val:
                while head and cur == head.val:
                    head = head.next
                pre.next = head
            else:
                pre = head
                head = head.next
        return dummy.next

reverse-linked-list

反转一个单链表。

思路：将当前结点放置到头结点

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        
        if head is None:
            return head
        
        tail = head
        while tail.next is not None:
            # put tail.next to head  
            tmp = tail.next
            tail.next = tail.next.next
            tmp.next = head
            head = tmp
        
        return head

Recursive method is tricky

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        
        if head is None or head.next is None:
            return head
        
        rev_next = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        
        return rev_next

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre = None
        while head:
            temp = head.next
            head.next = pre
            pre = head
            head = temp
        return pre

reverse-linked-list-ii

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

思路：先找到 m 处, 再反转 n - m 次即可

class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        
        if head is None:
            return head
        
        n -= m # number of times of reverse
        
        curr = dummy = ListNode(next=head)
        while m > 1: # find node at m - 1
            curr = curr.next
            m -= 1
        
        start = curr.next
        while n > 0: # reverse n - m times
            tmp = start.next
            start.next = tmp.next
            tmp.next = curr.next
            curr.next = tmp
            n -= 1
        return dummy.next

class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        if not head.next:
            return head
        dummy = ListNode()
        dummy.next = head
        pre = dummy
        count = 1
        while count < left:
            pre = head
            head = head.next
            count += 1
        cur = pre
        start = head
        while count <= right:
            temp = head.next
            head.next = cur
            cur = head
            head = temp
            count += 1
        pre.next = cur
        start.next = head
        return dummy.next

merge-two-sorted-lists

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

思路：通过 dummy node 链表，连接各个元素

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        
        tail = dummy = ListNode()
        while l1 is not None and l2 is not None:
            if l1.val > l2.val:
                tail.next = l2
                l2 = l2.next
            else:
                tail.next = l1
                l1 = l1.next
            tail = tail.next
                
        if l1 is None:
            tail.next = l2
        else:
            tail.next = l1

        return dummy.next

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode()
        head = dummy
        while l1 and l2:
            if l1.val < l2.val:
                head.next = l1
                l1 = l1.next
            else:
                head.next = l2
                l2 = l2.next
            head = head.next
        if l1:
            head.next = l1
        if l2:
            head.next = l2
        return dummy.next

partition-list

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

思路：将大于 x 的节点，放到另外一个链表，最后连接这两个链表

class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        
        p = l = ListNode()
        q = s = ListNode(next=head)
        
        while q.next is not None:
            if q.next.val < x:
                q = q.next
            else:
                p.next = q.next
                q.next = q.next.next
                p = p.next
        
        p.next = None
        q.next = l.next
        
	return s.next

哑巴节点使用场景

当头节点不确定的时候，使用哑巴节点

class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        if not head or not head.next:
            return head
        s_head = s = ListNode(next=head)
        l_head = l = ListNode()
        while s.next:
            if s.next.val < x:
                s = s.next
            else:
                l.next = s.next
                s.next = s.next.next
                l = l.next
        l.next = None
        s.next = l_head.next
        return s_head.next

sort-list

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

思路：归并排序，slow-fast找中点

class Solution:
    
    def _merge(self, l1, l2):
        tail = l_merge = ListNode()
        
        while l1 is not None and l2 is not None:
            if l1.val > l2.val:
                tail.next = l2
                l2 = l2.next
            else:
                tail.next = l1
                l1 = l1.next
            tail = tail.next

        if l1 is not None:
            tail.next = l1
        else:
            tail.next = l2
        
        return l_merge.next
    
    def _findmid(self, head):
        slow, fast = head, head.next
        while fast is not None and fast.next is not None:
            fast = fast.next.next
            slow = slow.next
        
        return slow
    
    def sortList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        
        mid = self._findmid(head)
        tail = mid.next
        mid.next = None # break from middle
        
        return self._merge(self.sortList(head), self.sortList(tail))

注意点

快慢指针判断 fast 及 fast.Next 是否为 nil 值
递归 mergeSort 需要断开中间节点
递归返回条件为 head 为 nil 或者 head.Next 为 nil

class Solution:
    def middle(self, head):
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow  

    def merge(self, l1, l2):
        head = l = ListNode()
        while l1 and l2:
            if l1.val < l2.val:
                l.next = l1
                l1 = l1.next
            else:
                l.next = l2
                l2 = l2.next
            l = l.next
        if l1:
            l.next = l1
        if l2:
            l.next = l2           
        return head.next

    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        mid = self.middle(head)
        sec = mid.next
        mid.next = None
        return self.merge(self.sortList(head), self.sortList(sec))

reorder-list

给定一个单链表 L：L→L→…→L__n→L 将其重新排列后变为： L→L__n→L→L__n→L→L__n→…

思路：找到中点断开，翻转后面部分，然后合并前后两个链表

class Solution:
    
    def reverseList(self, head: ListNode) -> ListNode:
        
        prev, curr = None, head
        
        while curr is not None:
            curr.next, prev, curr = prev, curr, curr.next
            
        return prev
    
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        if head is None or head.next is None or head.next.next is None:
            return
        
        slow, fast = head, head.next
        while fast is not None and fast.next is not None:
            fast = fast.next.next
            slow = slow.next
        
        h, m = head, slow.next
        slow.next = None
        
        m = self.reverseList(m)
        
        while h is not None and m is not None:
            p = m.next
            m.next = h.next
            h.next = m
            h = h.next.next
            m = p
            
        return

class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        if not head or not head.next:
            return head

        slow = l1 = head
        fast = head.next
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        cur = slow.next
        pre = None
        slow.next = None

        while cur:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp

        while l1 and pre:
            tpre = pre.next
            pre.next = l1.next
            l1.next = pre
            l1 = l1.next.next
            pre = tpre

        return head

linked-list-cycle

给定一个链表，判断链表中是否有环。

思路1：Hash Table 记录所有结点判断重复，空间复杂度 O(n) 非最优，时间复杂度 O(n) 但必然需要 n 次循环
思路2：快慢指针，快慢指针相同则有环，证明：如果有环每走一步快慢指针距离会减 1，空间复杂度 O(1) 最优，时间复杂度 O(n) 但循环次数小于等于 n

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        
        slow = fast = head
        
        while fast is not None and fast.next is not None:
            slow = slow.next
	    fast = fast.next.next
            if fast == slow:
                return True
        
        return False

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        slow = head
        fast = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return True
        return False

linked-list-cycle-ii

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

思路：快慢指针，快慢相遇之后，慢指针回到头，快慢指针步调一致一起移动，相遇点即为入环点。

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        
        slow = fast = head
        
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next
            
            if slow == fast:
                slow = head
                while fast != slow:
                    fast = fast.next
                    slow = slow.next
                return slow

        return None

坑点

指针比较时直接比较对象，不要用值比较，链表中有可能存在重复值情况
第一次相交后，快指针需要从下一个节点开始和头指针一起匀速移动

注意，此题中使用 slow = fast = head 是为了保证最后找环起始点时移动步数相同，但是作为找中点使用时一般用 fast=head.Next 较多，因为这样可以知道中点的上一个节点，可以用来删除等操作。

fast 如果初始化为 head.Next 则中点在 slow.Next
fast 初始化为 head,则中点在 slow

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        fast = slow = head
        while fast and fast.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

palindrome-linked-list

请判断一个链表是否为回文链表。

思路：O(1) 空间复杂度的解法需要破坏原链表（找中点 -> 反转后半个list -> 判断回文），在实际应用中往往还需要复原（后半个list再反转一次后拼接），操作比较复杂，这里给出更工程化的做法

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        
        s = []
        slow = fast = head
        while fast is not None and fast.next is not None:
            s.append(slow.val)
            slow = slow.next
            fast = fast.next.next
        
        if fast is not None:
            slow = slow.next
        
        while len(s) > 0:
            if slow.val != s.pop():
                return False
            slow = slow.next
            
        return True

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        slow = head
        fast = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        pre = None
        while slow:
            temp = slow.next
            slow.next = pre
            pre = slow
            slow = temp
        while pre:
            if head.val == pre.val:
                pre = pre.next
                head = head.next
            else:
                return False
        return True

copy-list-with-random-pointer

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深拷贝。

思路1：hash table 存储 random 指针的连接关系

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        
        if head is None:
            return None
        
        parent = collections.defaultdict(list)
        
        out = Node(0)
        o, n = head, out
        while o is not None:
            n.next = Node(o.val)
            n = n.next
            if o.random is not None:
                parent[o.random].append(n)
            o = o.next
            
        o, n = head, out.next
        while o is not None:
            if o in parent:
                for p in parent[o]:
                    p.random = n
            o = o.next
            n = n.next
        
        return out.next

思路2：复制结点跟在原结点后面，间接维护连接关系，优化空间复杂度，建立好新 list 的 random 链接后分离

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        
        if head is None:
            return None
        
        p = head
        while p is not None:
            p.next = Node(p.val, p.next)
            p = p.next.next
        
        p = head
        while p is not None:
            if p.random is not None:
                p.next.random = p.random.next
            p = p.next.next
        
        new = head.next
        o, n = head, new
        while n.next is not None:
            o.next = n.next
            n.next = n.next.next
            o = o.next
            n = n.next
        o.next = None
        
        return new

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return None
        copy = {}
        m = n = head
        while m:
            copy[m] = Node(m.val)
            m = m.next
        while n:
            if n.next:
                copy[n].next = copy[n.next]
            if n.random:
                copy[n].random = copy[n.random]
            n = n.next
        return copy[head]

总结

链表必须要掌握的一些点，通过下面练习题，基本大部分的链表类的题目都是手到擒来~

null/nil 异常处理
dummy node 哑巴节点
快慢指针
插入一个节点到排序链表
从一个链表中移除一个节点
翻转链表
合并两个链表
找到链表的中间节点

GeezerVison

Expand file tree

linked_list.md

Latest commit

History