【LeetCode】面試算法總結@連結清單

面試算法總結：連結清單

• 1、LeetCode----206. 連結清單翻轉
• • Solution1
  • Solution2
• 2、LeetCode----24. 兩兩交換連結清單中的節點
• • 基本思路
• 3、LeetCode----141. 環形連結清單
• • 基本思路
• 4、LeetCode----142. 環形連結清單 II
• • 基本思路

點選了解基本資料結構

1、LeetCode----206. 連結清單翻轉

https://leetcode-cn.com/problems/reverse-linked-list/

Solution1

#基本思路
#首先将連結清單中的所有的資料讀取存儲到清單中
#然後結合ListNode，将清單的倒序填充到新的建立的連結清單中
#不斷地插入後置節點，并不斷的填充val，直至清單的所有資料填充完畢
class ListNode:
   def __init__(self, x):
       self.val = x
       self.next = None
 
class Solution1:
    def reverseList(self, head: ListNode) -> ListNode:
        answer_val = []
        if not head:
            return head
        while head:
            answer_val.append(head.val)
            head = head.next
        answer_val = answer_val[::-1]
        new_head = ListNode(answer_val[0])
        answer_val.remove(answer_val[0])
        p = new_head
        for i in answer_val:
            temp = ListNode(i)
            p.next = temp
            p = p.next   
        return new_head
           

Solution2

#基本思路
#直接利用連結清單的特性進行構造将連結清單的前驅和後繼互換即可
class Solution2:
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        p, rev = head, None
        while p:
            rev, rev.next, p = p, rev, p.next
        return rev
           

2、LeetCode----24. 兩兩交換連結清單中的節點

https://leetcode-cn.com/problems/swap-nodes-in-pairs/submissions/

基本思路

#利用一個flag值将連結清單區分為奇數和偶數
#對連結清單進行分組，每兩個進行一組
#不斷地交換每一組中的前後兩個資料
#奇數時最後一個元素不進行交換
#Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        p, v = head, None
        flag = 0
        if not head or not head.next:
            return head
        while p:
            try:
                if not flag % 2:
                    v = p.next
                    p.val, v.val = v.val, p.val
            except:
                pass
            flag += 1
            p = p.next
        return head
           

3、LeetCode----141. 環形連結清單

https://leetcode-cn.com/problems/linked-list-cycle/

基本思路

#利用兩個指針，分别指向連結清單的頭部，兩個指針以不同的速度向前移動
#一個移動一次移動一位，一個一次移動兩位
#最後判斷，如果存在兩個指針的後繼指向同一個節點，那麼說明此為循環連結清單。
#Definition for singly-linked list.
# 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
        """
        other_head = head
        while head:
            try:
                head = head.next
                other_head = other_head.next.next
                if head.next == other_head.next:
                    return True
            except:
                return False
        return False
           

4、LeetCode----142. 環形連結清單 II

https://leetcode-cn.com/problems/linked-list-cycle-ii/

基本思路

#利用set資料結構的唯一性，将已經通路過的資料存入的set表中
#當出現head在set表中時此時說明此節點為再次出現的節點
#是以這個節點就肯定是我們要找的環形連結清單的起點
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution(object):
    def detectCycle(self, head):
        set1=set([])
        while head not in set1:
            set1.add(head)
            if not head:
                break
            head=head.next
        return head