Leetcode 链表专辑

链表的几个常见 Tips:

  • 通过 dummy head 来简化代码
  • while p 的代码要注意死循环
  • 提前问清楚有没有环这种特殊情况,一般会提前说清楚
  • 一定不要忘记移动指针

19. Remove Nth Node From End of List

移除从后往前数的第 N 个节点。
注意点:

  • 如果删除的是 head 节点,需要单独处理。这里可以通过 dummy head 的方式来简化代码
  • 要检查 n 是否越界,这里题目中声明 n 总是合法的
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        fast = dummy
        slow = dummy
        
        count = 0
            
        while fast.next:
            fast = fast.next
            if count < n:
                count += 1
            else:
                slow = slow.next
            
        slow.next = slow.next.next
        
        return dummy.next

142. Linked List Cycle II

https://leetcode.com/problems/linked-list-cycle-ii/
寻找链表中环的起点。
注意点:

  • p1 == p2 的两个判断,一个在移动之后,防止起点重合误判断,一个在移动之前,防止漏了起点重合
  • while else 这个语法很方便,可以判断是 while false 了还是 if break 了
class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        p1 = head
        p2 = head
        
        while p1 and p2 and p2.next:
            p1 = p1.next
            p2 = p2.next.next
            if p1 == p2:
                break
        else:
            return None
        
        p2 = head
        while p1 and p2:
            if p1 == p2:
                return p1
            p1 = p1.next
            p2 = p2.next
        return None

148. Sort List

链表排序。
参考归并排序可以解决。

def merge(p1, p2):
    dummy = ListNode(0)
    p = dummy
    
    while p1 and p2:
        if p1.val <= p2.val:
            p.next = p1
            p1 = p1.next
        else:
            p.next = p2
            p2 = p2.next
        p = p.next
        
    if p1:
        p.next = p1
    if p2:
        p.next = p2
        
    return dummy.next
        

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        
        p1 = head
        p2 = head
        prev = None
        while p2 and p2.next:
            prev = p1
            p1 = p1.next
            p2 = p2.next.next
        prev.next = None
        
        left = self.sortList(head)
        right = self.sortList(p1)
        return merge(left, right)

160. Intersection of Two Linked Lists

寻找两个链表的交点。
比较巧妙的做法是通过 p1 != p2 来判断是否结束,就算两个没有 intersection,也会都指向 None 结束循环。

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        p1 = headA
        p2 = headB
        
        while p1 != p2:
            p1 = p1.next if p1 else headB
            p2 = p2.next if p2 else headA
        
        return p1

206. Reverse Linked List

反转链表。

# 非递归解法,注意 p.next, prev, p = prev, p, p.next 这个顺序
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        p = head
        while p:
            p.next, prev, p = prev, p, p.next
        return prev


# 递归解法,利用 head.next 是 reverse 的最后一个元素这个特性。
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        left = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        
        return left

234. Palindrome Linked List

判断链表是否是对称的。
单双指针往后走,p1 边走边反转,最好是走完了再把链表还原回去。
注意这里 p1 和 p2 ,如果 p2 为 None,则 p1 是偶数右侧点,否则, p1 是奇数中点。

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        p1 = head
        p2 = head
        prev = None
        
        while p2 and p2.next:
            p2 = p2.next.next
            prev, p1.next, p1 = p1, prev, p1.next
        
        l = prev
        r = p1.next if p2 else p1
        prev = p1 if p2 else l
        while l and r:
            if l.val != r.val:
                return False
            r = r.next
            prev, l.next, l = l, prev, l.next
            
        return l == None

328. Odd Even Linked List

把链表拆分成奇偶链表,两个指针单次遍历做拆分。

class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        
        p1 = head
        p2 = head.next
        p2head = p2
        
        while p2 and p2.next:
            p1.next = p1.next.next
            p2.next = p2.next.next
            p1 = p1.next
            p2 = p2.next
            
        p1.next = p2head
        
        return head