leetcode刷題之鏈表必刷題（python實作）

最近重新回顧了一下鏈表，在自己手動寫了鏈表的生成以及相應的增刪查改操作后，對鏈表的理解更加深刻，于是在leetcode上刷了對應的習題，

王爭老師列舉了一些鏈表必刷題，感覺有必要做一下這些習題，

鏈表的必刷題有：

• 單鏈表反轉
• 鏈表中環的檢測
• 兩個有序的鏈表合并
• 洗掉鏈表倒數第n個結點
• 求鏈表的中間結點

206. 反轉鏈表

這道題可以用迭代或者遞回實作，

遞回和迭代的思路都是不斷反轉兩個節點，

遞回實作：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # 有一個節點或者沒有節點時，直接回傳串列
        if not head or not head.next:
            return head

        pre, node = head, head.next
        while node:
            pre, node = self.__reverse_two(pre, node)
        
        head.next = None
        head = pre
        return head

    def __reverse_two(self, pre, node):
        # 反轉兩個節點
        tmp = node.next
        node.next = pre
        pre, node = node, tmp
        return pre, node

迭代實作

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        pre, node = head, head.next
        while node:
            temp = node.next
            node.next = pre
            pre = node
            node = temp
        
        head.next = None
        return pre

92. 反轉鏈表 II

反轉鏈表92的題目可以在反轉鏈表206的題目上修改，

反轉的邏輯可以復用，

這里主要是要找到反轉的起始節點和終止節點，同時要保存剩下的節點，

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def reverseBetween(self, head, left, right):
        """
        :type head: ListNode
        :type left: int
        :type right: int
        :rtype: ListNode
        """
        if not head.next:
            return head
        
        fake_head = ListNode(-1)
        fake_head.next = head
        pre = fake_head
        # 得到反轉起始節點的前向節點
        for i in range(left - 1):
            pre = pre.next

        reverse_end = pre
        # 得到反轉終止節點
        for i in range(right - left + 1):
            reverse_end = reverse_end.next
        
        # 剩余不反轉的節點
        end_node = reverse_end.next
        # 反轉起始節點
        reverse_start = pre.next
        # 反轉終止節點指向None， 反轉起始節點的前向節點指向None
        reverse_end.next = None
        pre.next = None

        # 反轉中間部分的節點
        # 反轉起始節點reverse_start, 終止是 reverse_end
        pre_, node_ = reverse_start, reverse_start.next
        while node_:
            pre_, node_ = self.__reverse(pre_, node_)
        
        pre.next = pre_
        reverse_start.next = end_node
        return fake_head.next

    # 利用遞回反轉，也可以使用迭代
    def __reverse(self, pre, node):
        tmp = node.next
        node.next = pre
        pre, node = node, tmp
        return pre, node

劍指 Offer 22. 鏈表中倒數第k個節點

求倒數第k個節點有兩種方法，第一種是使用快慢指標，第二種就是先求出鏈表的長度，再遍歷得到對應節點

使用快慢指標

使用快慢指標可以只掃描一次，

# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getKthFromEnd(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        
        fast = slow = head
        # 快指標先走k步
        for i in range(k):
            fast = fast.next
        while fast:
            slow = slow.next
            fast = fast.next
        # 當快指標走完的時候，慢指標就位于該節點
        return slow

先遍歷再取節點

# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getKthFromEnd(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if not head or not head.next:
            return head

        # 先求出鏈表長度
        n = 0
        p = head
        while p:
            p = p.next
            n += 1
        
        # 遍歷找到k的位置
        pos = 0
        p = head
        while p and k != (n - pos):
            p = p.next
            pos += 1
        return p

19. 洗掉鏈表的倒數第 N 個結點

洗掉倒數第n個節點也可以使用快慢指標的思路，

# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        # 沒有節點或者只有一個節點時直接回傳
        if not head or not head.next:
            return head
        
        fast = slow = head
        # 快指標先走n步
        for i in range(n):
            fast = fast.next

        # pre指標用于找到倒數第n個節點的前向節點
        pre = ListNode(-1)
        while fast:
            pre.next = slow
            slow = slow.next
            fast = fast.next
            pre = pre.next

        pre.next = slow.next
        return head

876. 鏈表的中間結點

采用的方法是先求鏈表長度，再求中間節點，或者快慢指標，
感覺這道題和求倒數第n節點的思想都差不多

快慢指標法

快指標比慢指標多走兩步，當快指標走完時，慢指標指向的節點就是中間節點

# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def middleNode(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

先遍歷再求節點

# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def middleNode(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        n = 0
        p = head
        while p:
            p = p.next
            n += 1

        mid = n // 2
        p = head
        pos = 0
        while p and pos != mid:
            p = p.next
            pos += 1
        return p

21. 合并兩個有序鏈表

兩個鏈表分別用指標遍歷

# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        fake_head = ListNode(-1)
        pre = fake_head
        while l1 and l2:
            if l1.val <= l2.val:
                pre.next = l1
                l1 = l1.next
            else:
                pre.next = l2
                l2 = l2.next
            pre = pre.next  # 寫代碼的時候遺漏了該指標的移動
        # 剩余節點
        pre.next = l1 or l2
        return fake_head.next

141. 環形鏈表

這道題也是使用快慢指標，如果有環，快慢指標最終相遇，

快指標始終比慢指標多走一步

# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        # 加上這個判斷之后時間更快了
        if not head or not head.next:
            return False

        fast = slow = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            # 快慢指標相遇說明存在環
            if slow == fast:
                return True
        return False

142. 環形鏈表 II

這道題也使用快慢指標，只不過還需要看相遇的節點是第幾個節點，

# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return None
        
        fast = slow = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                pre = head
                while pre != slow:
                    pre = pre.next
                    slow = slow.next
                return pre
        return None