算法工程師面試必考項(xiàng)——鏈表

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

class Solution:    def deleteDuplicates(self, head: ListNode) -> ListNode:        if not head or not head.next:  # 空鏈表或單即節(jié)點(diǎn)鏈表            return head
        dummy = ListNode(0)    # 定義啞節(jié)點(diǎn)        dummy.next = head        pre = dummy            # 啞節(jié)點(diǎn)指針        cur = head             # 鏈表指針        flag = False           # 標(biāo)記是否重復(fù)        while cur:            while cur.next and pre.next.val == cur.next.val:                cur = cur.next   # 將所有重復(fù)節(jié)點(diǎn)標(biāo)記為True                flag = True            if flag is True:     # 重復(fù)節(jié)點(diǎn)就跳過                pre.next = cur.next                flag = False            else:                pre = cur        # 不重復(fù)就下一個節(jié)點(diǎn)            cur = cur.next        return dummy.next

# 迭代class Solution:    def reverseList(self, head: ListNode) -> ListNode:        pre = None        cur = head        while cur:            temp = cur.next   # 存儲節(jié)點(diǎn)的下一位            cur.next = pre    # 指向前驅(qū)節(jié)點(diǎn)            pre = cur                     cur = temp        # cur指向原來的下一位        return pre

# 遞歸class Solution:    def reverseList(self, head: ListNode) -> ListNode:        if not head or not head.next:            return head        p = self.reverseList(head.next)        head.next.next = head        head.next = None        return p

class Solution:    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:        dummy = ListNode(None)        dummy.next = head        pre = dummy        for i in range(1, m):            pre = pre.next         # 前驅(qū)指針移動到位置m        cur = pre.next        for i in range(m, n):      # 兩兩交換節(jié)點(diǎn)            temp = cur.next                    cur.next = temp.next   # cur一直不變，只修改指針到下一個位置            temp.next = pre.next   # temp.next指向pre的next，也就是最新的第m個位置            pre.next = temp        # 更新temp為最新的第m個位置        return pre

class Solution:    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:        dummy = ListNode(None)        pre = dummy        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 if l1 else l2        return dummy.next

class Solution:    def partition(self, head: ListNode, x: int) -> ListNode:        before = befornHead = ListNode(None)        after = afterHead = ListNode(None)        while head:            if head.val < x:                before.next = head                before = before.next            else:                after.next = head                after = after.next            head = head.next            after.next = None        before.next = afterHead.next        return befornHead.next

# 歸并排序（遞歸），空間復(fù)雜度O(n)class Solution:    def sortList(self, head: ListNode) -> ListNode:        if not head or not head.next:            return head        slow, fast = head, head.next        while fast and fast.next:            slow, fast = slow.next, fast.next.next        mid = slow.next        slow.next = None        left = self.sortList(head)        right = self.sortList(mid)        h = res = ListNode(0)        while left and right:            if left.val < right.val:                 h.next, left = left, left.next            else:                 h.next, right = right, right.next            h = h.next        h.next = left if left else right        return res.next

# 快速排序class Solution:    def sortList(self, head: ListNode) -> ListNode:        if head is None:            return head        # 分成三個鏈表，分別是比軸心數(shù)小，相等，大的數(shù)組成的鏈表        big = None        small = None        equal = None        cur = head        while cur:            temp = cur            cur = cur.next            if temp.val < head.val:                temp.next = small                small = temp            elif temp.val > head.val:                temp.next = big                big = temp            else:                temp.next = equal                equal = temp        # 拆完各自排序即可，equal 無需排序        big = self.sortList(big)        small = self.sortList(small)
        ret = ListNode(None)        cur = ret        # 將三個鏈表組合成一起        # 可以同時返回鏈表的頭指針和尾指針加速鏈表的合并。        for p in [small, equal, big]:            while p is not None:                cur.next = p                p = p.next                cur = cur.next            cur.next = None        return ret.next

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, fast = head, head        # 找到鏈表中點(diǎn)        while fast.next and fast.next.next:               slow = slow.next            fast = fast.next.next        # 反轉(zhuǎn)后半部分        print(slow.next)        right = None        cur = slow.next        while cur:            temp = cur.next            cur.next = right            right = cur            cur = temp        # 將反轉(zhuǎn)的后半部分插入到前半部分        left = head        while left and right:            slow.next = right.next            right.next = left.next            left.next = right            left = right.next            right = slow.next

# 哈希表class Solution:    def hasCycle(self, head: ListNode) -> bool:        dic = {}        while head:            if head in dic:                return True            else:                dic[head] = 1            head = head.next        return False

# 快慢指針class Solution:    def hasCycle(self, head: ListNode) -> bool:        if head is None or head.next is None:            return False        slow = head        fast = slow.next        while fast and fast.next:            fast = fast.next.next            slow = slow.next            if fast == slow:                return True        return False

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

class Solution:    def copyRandomList(self, head: 'Node') -> 'Node':        if not head:            return        dic = {}        dic[None] = None        cur = head        while cur:            if cur not in dic:                dic[cur] = Node(cur.val)     # 將當(dāng)前未拷貝的節(jié)點(diǎn)放入字典中            if cur.random not in dic:                dic[cur.random] = Node(cur.random.val)   # 將當(dāng)前未拷貝的random指針放入字典中            dic[cur].random = dic[cur.random]            if cur.next not in dic:                dic[cur.next] = Node(cur.next.val)     # 將當(dāng)前未拷貝的next指針放入字典中            dic[cur].next = dic[cur.next]            cur = cur.next        return dic[head]

# 將值復(fù)制到數(shù)組中class Solution:    def isPalindrome(self, head: ListNode) -> bool:        visit = []        cur = head        while cur:            visit.append(cur.val)            cur = cur.next        return visit == visit[::-1]

# 找中點(diǎn) -> 反轉(zhuǎn) -> 比較class Solution:    def isPalindrome(self, head: ListNode) -> bool:        pre = None        slow, fast = head, head        while fast and fast.next:            slow = slow.next      # 使慢指針指向中間節(jié)點(diǎn)            fast = fast.next.next        while slow:  # 反轉(zhuǎn)后半部分，pre指向反轉(zhuǎn)部分            temp = slow.next            slow.next = pre            pre = slow            slow = temp        while head and pre:   # 比較兩部分是否相同            if head.val != pre.val:                return False            head = head.next            pre = pre.next        return True