Leetcode: Linked List

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

206 Reverse Linked List

class Solution:
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        cur, pre = head, None
        while cur:
            #    ,   pre  
            cur.next, pre, cur = pre, cur, cur.next
        return pre

24 Swap Nodes in Pairs

class Solution:
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        pre, pre.next = self, head
        while pre.next and pre.next.next:
            a = pre.next
            b = a.next
      		#         : pre->a->b->c, pre->b->a->c
            pre.next, b.next, a.next = b, a, b.next
            #   pre    
            pre = pre.next.next

        return self.next

141 Linked List Cycle

法一:各ノードの値を集合で記録し、同時に重量を調べる.O(n)の空間時間複雑度

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        # init
        d = set()
        p = head
        while p and p.next:
            if p not in d: # search
                d.add(p) # insertion
                p = p.next # move
            else:
                return True
        return False

法二:二重ポインタ、二つのポインタの移動速度は速くて遅い.O(1)の空間的複雑度,O(N)の時間的複雑度

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
		slow = fast = head
        while fast and fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

142 Linked List Cycle II
前の2つの方法と同じで、その中の2つのポインタの方法、多く絵を描くことができて1つの法則を発見することができます:反復回数は一環の点数に等しいです.そこでここでは,ヘッダノードからループ入口までが出会い点と等しくループ入口に再び到達することを知ることができ,この式を用いてこの問題を解くことができる.

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # set method
        d = set()
        p = head
        while p:
            if p not in d:
                d.add(p)
                p = p.next
            else:
                return p         
        return None

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # two pointer
        slow = fast = head   
        while fast and fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
            #     ，      ，    1      ，        
            if slow == fast:
                slow = head
                while slow != fast:
                    slow = slow.next
                    fast = fast.next
                return slow
        return None

25 Reverse Nodes in k-Group

class Solution:
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        pre, pre.next = self, head
        while 1:
            #        k        
            temp = []            
            for i in range(k):
                temp.append(pre.next)
                if pre.next == None:
                    pre.next = temp[0]
                    return self.next
                pre.next = pre.next.next
            # pre.next = head
            # exchange node
            tempp = temp[-1].next #             
            pre.next = temp[-1] #             
            for i in range(k-1,0,-1): #           
                temp[i].next = temp[i-1]
            temp[0].next = tempp #    20      
            # move pre
            for i in range(k):
                pre = pre.next

まとめると、チェーンテーブルの問題は、通常、操作のセットを完了した後、whileからテーブルの最後までです.境界問題に注意すべきで、いくつかの問題は少し巻いて、鎖は鎖に来て、解く時に何回かの反復を描くことができます.