LeetCode：鏈表（1）

劍指offer 06.從頭到尾列印鏈表

思路1：使用堆疊的概念

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        lst = []
        while head:
            lst.insert(0,head.val)
            head=head.next
        return lst

運行時間較高；經過分析發現insert時間復雜度O(n)
改進

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        lst = []
        while head:
            lst.append(head.val)
            head=head.next
        return lst[::-1]

有明顯改善

方法2：遞回法

• 1.遞推階段： 每次傳入 head.next ，以 head == None（即走過鏈表尾部節點）為遞回終止條件，此時回傳空串列 [] ，
• 2.回溯階段： 利用 Python 語言特性，遞回回溯時每次回傳 當前 list + 當前節點值 [head.val] ，即可實作節點的倒序輸出，

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        return self.reversePrint(head.next) + [head.val] if head else []

劍指offer 18.洗掉鏈表的節點

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        
        prevNode = head
        res = prevNode
        if head.val == val:
            prevNode = head.next
            return prevNode
        else:
            while head:
                if head.val == val:
                    prevNode.next = head.next
                    return res
                prevNode = head
                head = head.next

83.洗掉排序鏈表中的重復元素

# 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:
        if head == None or head.next == None:
            return head
        else:
            pre,node = head,head.next
            res = pre
            while node:
                if node.val == pre.val:
                    node = node.next
                    if node == None:
                        pre.next = node
                else:
                    pre.next = node
                    pre=pre.next
                    node =node.next
        return res

改進（思路沒變）

# 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:
        if  not head:
            return head
        pre,node = head,head.next
        while node:
            if node.val == pre.val:
                node = node.next
                if node == None:
                    pre.next = node
            else:
                pre.next = node
                pre=pre.next
                node =node.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:
        if not head: return None
        prev,cur = head,head.next
        while cur:
            if prev.val==cur.val:
                prev.next = cur.next
            else:
                prev=cur
            cur=cur.next
        return head

141.環形鏈表

快慢指標

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

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

思路2：遞回標記法

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if head is None:
            return False
        if head.val == '0':
            return True
        head.val = '0'
        return self.hasCycle(head.next)

思路3：字典模擬hash查找
dict.get(key, default=None)

• key – 字典中要查找的鍵，
• default – 如果指定鍵的值不存在時，回傳該默認值，默認為None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        dic = {}
        node = head
        while node:
            if dic.get(node)!=None:#如果不存在get回傳的是0
                return True
            else:
                dic[node] = 1
            node = node.next
        return False