LC.19 Remove Nth Node Form End of List

Description

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

Solution

• one-pass (trivial) 實(shí)際上有兩個(gè)指針肠缨，所以是2-pass

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

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        count = 1
        target = head
        temp = head
        while count < n:
            temp = temp.next
            count += 1
        if temp.next == None:
            return target.next
        else:
            temp = temp.next
        while temp.next != None:
            target = target.next
            temp = temp.next
        target_d = target.next
        target.next = target_d.next
        
        return head
        

• recursive

  # Definition for singly-linked list.
  # class ListNode:
  #     def __init__(self, x):
  #         self.val = x
  #         self.next = None
  
  class Solution:
      def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
          rec = self.helper(head, n)
          if rec == n:
              return head.next
          return head
      
      def helper(self, head: ListNode, n: int) -> int:
          if head.next == None:
              return 1
          rec = self.helper(head.next, n)
          if rec == n:
              head.next = head.next.next
          return rec + 1
  

  遞歸做法榄笙，實(shí)際上這道題本質(zhì)上必須遍歷整個(gè)鏈表直到最后一個(gè)node揍移，所以用遞歸的方法查看之后還剩多少個(gè)元素盯桦，如果正好是n的話驻仅，那么當(dāng)前的結(jié)點(diǎn)(倒數(shù)第n+1個(gè))的下一個(gè)結(jié)點(diǎn)(倒數(shù)第n個(gè))就需要被刪除其徙。和另外一個(gè)方法比起來并不會(huì)增大memory的占用唯灵。runtime還更低（我猜是因?yàn)樯倭艘粋€(gè)移動(dòng)的指針）

LC.83 Remove Duplicates from Sorted List

Description

Given a sorted linked list, delete all duplicates such that each element appear only once.

Example 1:

Input: 1->1->2
Output: 1->2

Example 2:

Input: 1->1->2->3->3
Output: 1->2->3

Solution

• straight solution (兩個(gè)指針)

• # Definition for singly-linked list.
  # class ListNode:
  #     def __init__(self, x):
  #         self.val = x
  #         self.next = None
  
  class Solution:
      def deleteDuplicates(self, head: ListNode) -> ListNode:
          node_a = head
          node_b = head
          if head == None:
              return head
          while node_b.next != None:
              if node_b.val != node_b.next.val:
                  node_a.next = node_b.next
                  node_a = node_a.next
              node_b = node_b.next
          if not node_a == node_b:
              node_a.next = node_b.next
          return head
  

  或者一個(gè)指針：

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

• 遞歸做法

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

LC. 92 Reversed Linked List

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

Solution

• 直接從前往后走丰泊，只要還在reverse的范圍內(nèi)薯定，看見一個(gè)拎出來一個(gè)，添加到旁邊的翻轉(zhuǎn)新鏈表的表頭瞳购。所有需要翻轉(zhuǎn)的都翻轉(zhuǎn)完之后话侄，把新的鏈表插在原來的鏈表里面

  class Solution(object):
      def reverseBetween(self, head, m, n):
          """
          :type head: ListNode
          :type m: int
          :type n: int
          :rtype: ListNode
          """
          holder = ListNode(-1)
          holder.next = head
          head = holder
          count = 1
          while count < m:
              head = head.next
              count += 1
          new = None
          while count < n+1:
              temp = head.next.next
              head.next.next = new
              new = head.next
              if count == m:
                  tail = new
              head.next = temp
              count += 1
          temp = head.next
          head.next = new
          tail.next = temp
          return holder.next
  
  

  在表的最前面加一個(gè)holder可以方便計(jì)數(shù)，并且corner case少了很多Ｑ年堆！第17-20行是翻轉(zhuǎn)表頭的操作

• 遞歸做法

  class Solution(object):
      def reverseBetween(self, head, m, n):
          """
          :type head: ListNode
          :type m: int
          :type n: int
          :rtype: ListNode
          """
          self.successor = None
          if m == 1:
              return self.reverseHelper(head, n-m+1)
          head.next = self.reverseBetween(head.next, m-1, n-1)
          return head
              
      def reverseHelper(self, head, m):
          if m == 1:
              self.successor = head.next
              return head
          new = self.reverseHelper(head.next, m-1)
          head.next.next = head
          head.next = self.successor
          return new
  

  是LC.206的變形，遞歸的時(shí)候加入一個(gè)變量k盏浇，reverse當(dāng)前鏈表的前k個(gè)元素变丧。遞歸現(xiàn)在還寫得亂七八糟的！绢掰！

LC. 61 Rotate List

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

Solution

• 直接解：

  先數(shù)一下一共有多少個(gè)元素痒蓬，再用總數(shù)減去模k的值求left rotate多少個(gè)。找到新的頭元素滴劲，把tail和原來的頭元素串起來就好了

  class Solution(object):
      def rotateRight(self, head, k):
          """
          :type head: ListNode
          :type k: int
          :rtype: ListNode
          """
          if not head:
              return head
          count = 1
          key = head
          while key.next:
              count += 1
              key = key.next
          key.next = head
          k = count - k % count
          
          while k > 1:
              head = head.next
              k -= 1
          new = head.next
          head.next = None
          return new
  

• 還可以用間隔k的兩個(gè)指針攻晒，一旦走到頭就重新回到head的方法，不需要顯式地求list的長(zhǎng)度班挖。但這樣復(fù)雜度顯然變高了鲁捏，模掉的那堆都得計(jì)算一遍

LC. 143 Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list's nodes, only nodes itself may be changed.

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

Solutions

• 這題還蠻容易錯(cuò)的，主要是reverse list的時(shí)候不能反轉(zhuǎn)原鏈表萧芙，這樣正序的鏈表就沒了碴萧；首先找到鏈表中點(diǎn)乙嘀，然后反轉(zhuǎn)后一半的鏈表末购，前一半的鏈表a和后一半的反轉(zhuǎn)鏈表b交替插在一塊兒就好了

  class Solution(object):
      def reorderList(self, head):
          """
          :type head: ListNode
          :rtype: None Do not return anything, modify head in-place instead.
          """
          if not head or not head.next:
              return
          a = b = head
          move_a = False
          while b.next:
              b = b.next
              if move_a == True:
                  a = a.next
                  move_a = False
              else:
                  move_a = True
          list_b = self.reverseList(a.next)
          a.next = None
          list_a = head
          while list_b:
              a_temp = list_a.next
              b_temp = list_b.next
              list_a.next = list_b
              list_b.next = a_temp
              list_a = a_temp
              list_b = b_temp
          return
      
      def reverseList(self, head):
          if not head.next:
              return head
          new = self.reverseList(head.next)
          head.next.next = head
          head.next = None
          return new
  

  優(yōu)化：

  第7-17行可以優(yōu)化成如下破喻，復(fù)雜度降了好多，我也不確定為什么盟榴，大概是更改變量的次數(shù)變少了曹质。。

   while b.next.next:
              b = b.next.next
              a = a.next
              if not b.next:
                  break
  

• 感覺這道沒必要用遞歸擎场，因?yàn)槊看味嫉谜易钗捕说脑赜鸬拢詢r(jià)比很低 （？

LC. 21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4迅办、

Solutions

• 直接解（超級(jí)丑）

• class Solution(object):
      def mergeTwoLists(self, l1, l2):
          """
          :type l1: ListNode
          :type l2: ListNode
          :rtype: ListNode
          """
          if not l1:
              return l2
          if not l2:
              return l1
          if l1.val <= l2.val:
              head = l1
              l1 = l1.next
          else:
              head = l2
              l2 = l2.next
          key = head
          while l1 and l2:
              if l1.val <=l2.val:
                  key.next = l1
                  key = key.next
                  l1 = l1.next
              else:
                  key.next = l2
                  key = key.next
                  l2 = l2.next
          if l1 or l2:
              key.next = l1 if l1 else l2
          return head
  

• 遞歸（似乎叫動(dòng)態(tài)規(guī)劃了這里)

  class Solution(object):
      def mergeTwoLists(self, l1, l2):
          """
          :type l1: ListNode
          :type l2: ListNode
          :rtype: ListNode
          """
          if not l1:
              return l2
          if not l2:
              return l1
          if l1.val <= l2.val:
              l1.next = self.mergeTwoLists(l1.next, l2)
              return l1
          else:
              l2.next = self.mergeTwoLists(l1, l2.next)
              return l2
  

LC. 160. Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

Notes:

If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

Solutions

• 一個(gè)超簡(jiǎn)潔的解法：

  class Solution(object):
      def getIntersectionNode(self, headA, headB):
          """
          :type head1, head1: ListNode
          :rtype: ListNode
          """
          if not headA or not headB:
              return None
          
          a = headA
          b = headB
          while a != b:
              a = headB if a == None else a.next
              b = headA if b == None else b.next
          return a
  

  • 思路是a+b = b+a宅静，如果遍歷兩遍，他們會(huì)同時(shí)到達(dá)終點(diǎn)站欺，自動(dòng)對(duì)齊

  • 第12行很重要姨夹，這和兩個(gè)鏈表intersect的方式有關(guān)，如果只是一個(gè)node的val相同矾策，這個(gè)語(yǔ)句是false的磷账。必須后面是同一個(gè)鏈才是true

  • 第12行到14行的另外一種錯(cuò)誤寫法：

    if a.next == None:
        a.next = headB
    if b.next == None:
        b.next = headA
    a = a.next
    b = b.next
    

    原因是第2/4行會(huì)導(dǎo)致鏈表的終端不指向None，會(huì)形成一個(gè)環(huán)形鏈表贾虽，這樣后到達(dá)的指針就出不來了逃糟！

LC. 141. Linked List Cycle

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Solutions

• 一個(gè)作弊解法：（which 我覺得肯定有毛病）

  class Solution(object):
      def hasCycle(self, head):
          """
          :type head: ListNode
          :rtype: bool
          """
          marker = ListNode(-1)
          if not head:
              return False
          while head.next and not head.next == marker:
              temp = head.next
              head.next = marker
              head = temp
          if not head.next:
              return False
          return True
  

  走過的點(diǎn)就標(biāo)記為走過蓬豁，通過把它指向一個(gè)marker點(diǎn)绰咽。但這樣鏈表就被損壞了

• 龜兔賽跑的解法：一個(gè)指針以步長(zhǎng)1移動(dòng)，另一個(gè)以步長(zhǎng)2移動(dòng)地粪。如果有環(huán)的話取募，fast指針一定會(huì)追上另外一個(gè)

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

  這里用try/except的寫法寫會(huì)更快，不必每次顯式地檢查是否有指針到達(dá)終點(diǎn)

class Solution(object):
def insertionSortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head:
return head
helper = ListNode(0)
pre = helper

    while head:
        temp = head.next
        if pre.next and head.val < pre.next.val:
            pre = helper
        while pre.next and head.val >= pre.next.val:
            pre = pre.next
        head.next = pre.next
        pre.next = head
        head = temp
        
    return helper.next

LC. 138 Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Solution

• 交替索引

  class Solution(object):
      def copyRandomList(self, head):
          """
          :type head: Node
          :rtype: Node
          """
          if not head:
              return None
          helper = Node(0, head, None)
          while head.next:
              new = Node(head.val, head.next, head.random)
              head.next = new
              head = head.next.next
          new = Node(head.val, None, head.random)
          head.next = new
          
          new_head = helper.next.next
          while new_head.next:
              new_head.random = None if not new_head.random else new_head.random.next
              new_head = new_head.next.next
          new_head.random = None if not new_head.random else new_head.random.next
              
          head = helper.next
          helper.random = head.next
          new = Node(0, None, None)
          while head.next.next:
              new.next = head.next
              head.next = head.next.next
              new = new.next
              head = head.next
          new.next = head.next
          head.next = None
  
          return helper.random
  

• keep an hash table for each node in the list: 原鏈表的每一個(gè)node索引到它的copy上驶忌，然后再次從頭到位遍歷原來的鏈表矛辕，寫入新結(jié)點(diǎn)們的next和random

  class Solution(object):
      def copyRandomList(self, head):
          """
          :type head: Node
          :rtype: Node
          """
          if not head:
              return None
          copy = dict()
          m = n = head
          while m:
              copy[m] = Node(m.val, m.next, m.random)
              m = m.next
          while n:
              copy[n].next = copy.get(n.next)
              copy[n].random = copy.get(n.random)
              n = n.next
          return copy[head]
  

  需要注意的是，在第15/16行都用的是dict.get(key)而不是直接dict[key], 這是為了當(dāng)key等于None的時(shí)候付魔，返回default value None而不是報(bào)錯(cuò)聊品。如果事先定義copy[None]=None的話，這兩處也可以直接用dict[key]

  這種方法還有一個(gè)很trick的只遍歷一次的寫法几苍，使用collections.defaultdict來訪問(及創(chuàng)建)存在(或不存在)的結(jié)點(diǎn)

  class Solution(object):
      def copyRandomList(self, head):
          """
          :type head: Node
          :rtype: Node
          """
          copy = collections.defaultdict(lambda: Node(0, None, None))
          m = head
          copy[None] = None
          while m:
              copy[m].val = m.val
              copy[m].next = copy[m.next]
              copy[m].random = copy[m.random]
              m = m.next
          return copy(head)
  

  注意這里的12/13行是直接調(diào)用的方式翻屈，且在第9行定義了key=None的情況。這是因?yàn)楝F(xiàn)在的default是RandomNode(0)而不是None了

LC. 142 Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Solution

• hash table that records the visited nodes

  class Solution(object):
      def detectCycle(self, head):
          """
          :type head: ListNode
          :rtype: ListNode
          """
          info = dict()
          m = head
          while m:
              if not info.get(m):
                  info[m] = True
              else:
                  return m
              m = m.next
          return None
  

• hare-tortoise method

  class Solution(object):
      def detectCycle(self, head):
          """
          :type head: ListNode
          :rtype: ListNode
          """
          fast = slow = helper = head
          try:
              fast = fast.next.next
              slow = slow.next
              while not fast == slow:
                  fast = fast.next.next
                  slow = slow.next
              while not helper == slow:
                  helper = helper.next
                  slow = slow.next
              return helper
          except:
              return None
  

  這里最重要的就是fast步長(zhǎng)=2妻坝，slow=1伸眶。惊窖。。這樣保證了fast恰好超slow一圈