leetcode解题报告-链表

本贴最后更新于 1929 天前,其中的信息可能已经时移俗易

#前言
##链表的特点
链表的特点是只能从前往后进行顺序访问(当然还有双向链表和环,但到目前为止还未出现过双向链表),但是和可以随机访问的数组或列表对比起来,链表在插入,删除时不需要对后续节点进行操作,使时间复杂度大大降低。认清楚了链表的特点之后,我们就可以在特定的使用环境下,克服缺点发扬优点。

##链表题的特点
应该来说,链表题是广大刷题者又爱又恨的类型。爱是因为,链表题通常不会让人想破脑袋,leetcode 中的链表题都是简单的单链表(无双向链表),操作无是增删改查,排序,合并等基础问题。恨是因为,链表题通常很琐碎,需要考虑各种特殊情况和越界问题,代码不可避免地会比较长。

根据链表和链表题的特点我们通常也会有一些解题的小技巧:

  • 把顺序访问变成随机访问。
    这也是我最喜欢用的一种方法,把节点放到列表中。对于 python,这实现起来非常方便,python 的列表可以丢任何类型。
  • 很难修改节点,那就修改节点的值。
    这是我们很容易忽略的解法。修改节点(如删除或者改变节点顺序),若条件不足(如不知道前驱节点),我们可以尝试修改节点的值而不是节点本身。但需要注意题目是否禁止这样的做法。
  • 适当增加头指针,尾指针。
    增加头指针和尾指针可以很大程度减少我们的特殊条件,使代码行数减少,而且这也是一种好的习惯。

以下对 leetcode 的链表题进行汇总,基本都是常规的解法和思路。


#删除节点

##19.Remove Nth Node From End of List

  • 难度:Easy

  • 题目大意:
    给定一个链表,删除从末端算起的第 N 个节点,并返回头节点。假定 N 总是合理的。

  • 思路:
    最简单的思路是先扫一遍,获得链表的长度,这样第二次扫到需要删除的节点直接删除就可以。但是这样要遍历两次链表。
    还有一种解法只需要扫一遍,用三个指针 pre,cur,future 分别进行记录,pre 是 cur 的前序(删除节点需要记录前序),future 是探针,保持 futrue 比 cur 领先 N 个节点,当 future 指向尾节点时,cur 就是欲删除节点。
    这里,为了使当第 N 个节点为第一个结点时需要做特殊处理,特意加入了一个头结点。这也是链表题常用的方法。

  • 代码:

      # Definition for singly-linked list.
      class ListNode:
          def __init__(self, x):
              self.val = x
              self.next = None
    
      class Solution:
          # @param {ListNode} head
          # @param {integer} n
          # @return {ListNode}
          def removeNthFromEnd(self, head, n):
              pre = ListNode(0)
              pre.next = head
              cur = head
              head = pre
              while cur != None:
                  future = cur
                  for i in range(n-1)
                      future = future.next
                  if future.next == None:
                      pre.next = cur.next
                      return head.next
                  else:
                      pre = cur
                      cur = cur.next
    

##83. Remove Duplicates from Sorted List

  • 难度:Easy

  • 题目大意:
    给定一个已经排序的链表,删除所有值重复的节点。

  • 思路:
    常规的删除节点题目,比较下一节点是否和当前节点值一致,若是删除下一节点,若否向前推进。

  • 代码:

      class ListNode:
          def __init__(self, x):
              self.val = x
              self.next = None
    
      class Solution:
          # @param {ListNode} head
          # @return {ListNode}
          def deleteDuplicates(self, head):
              if not head:
                  return head
              c = head
              while c.next:
                  n = c.next
                  if n.val == c.val:
                      c.next = n.next
                  else:
                      c = c.next
              return head
    

##82. Remove Duplicates from Sorted List II

  • 难度:Medium

  • 题目大意:
    给定一个已排序链表,删除所有重复出现的节点,即若出现多个 1,则删除所有 1 的节点,而非留下一个 1。

  • 思路:
    这道题的难度明显就要比上一题的高出许多。我采取的思路是,一个变量 dup 记录当前正重复出现的节点值,用一个列表 nodes 记录所有不重复出现的节点。若当前节点值和 dup 相同,直接推进。若不同,则和列表 nodes 的最后一个节点比较,若不同,则加入列表并推进;若相同,则把列表最后一个节点删除,并把 dup 值设该重复节点的值,链表向前推进。最后重新连接列表中的节点即可。

  • 代码:

      # Definition for singly-linked list.
      # class ListNode(object):
      #     def __init__(self, x):
      #         self.val = x
      #         self.next = None
    
      class Solution:
          # @param {ListNode} head
          # @return {ListNode}
          def deleteDuplicates(self, head):
              if not head: return head
              dup = None
              nodes = []
              c = head
              while c:
                  if not dup or dup.val != c.val:
                      if not nodes or nodes[-1].val != c.val:
                          nodes.append(c)
                      else:
                          nodes.pop(-1)
                          dup = c
                  else:
                      dup = c
    
                  c = c.next
              for i in range(len(nodes)-1):
                  nodes[i].next = nodes[i+1]
              if nodes:
                  nodes[-1].next = None
                  return nodes[0]
              else:
                  return None
    

##203. Remove Linked List Elements

  • 难度:Easy

  • 题目大意:
    删除链表中所有值为 val 的节点。

  • 思路:
    常规删除节点的题目,需要注意若需要删除第一个节点怎么处理。这也是为什么大家通常为在链表中加入头结点的原因,这样可以不用考虑第一个节点。为了让大家更清楚看到这种特殊情况,下面给出代码中我没有加入头节点。

  • 代码:

      # Definition for singly-linked list.
      # class ListNode:
      #     def __init__(self, x):
      #         self.val = x
      #         self.next = None
    
      class Solution:
          # @param {ListNode} head
          # @param {integer} val
          # @return {ListNode}
          def removeElements(self, head, val):
              if not head:
                  return head
              cur = head
              while cur:
                  if head.val == val:
                      head = head.next
                      cur = head
                  elif cur.val == val:
                      cur = cur.next
                      pre.next = cur
                  else:
                      pre = cur
                      cur = cur.next
              return head
    

##237. Delete Node in a Linked List

  • 难度:Easy

  • 题目大意:
    给定链表中的某个节点(非尾节点),删除该节点。

  • 思路:
    只给定一个节点的话,我们是没办法删除这个节点的(需要知道这个节点的前驱),但是我们可以删除这个节点的 next 节点。观察题目,没有说不能改变节点的值,那么我们可以偷梁换柱,把该节点的值换为下一个节点的值,然后删除下一个节点。

  • 代码:

      # Definition for singly-linked list.
      # class ListNode(object):
      #     def __init__(self, x):
      #         self.val = x
      #         self.next = None
    
      class Solution(object):
          def deleteNode(self, node):
              """
              :type node: ListNode
              :rtype: void Do not return anything, modify node in-place instead.
              """
              if not node or not node.next:return
              node.val = node.next.val
              node.next = node.next.next
    


#翻转链表

##206.Reverse Linked List

  • 难度:Easy

  • 题目大意:
    翻转整个链表。

  • 思路:
    没什么可讲的,就地翻转必须熟记。

  • 代码:

      # Definition for singly-linked list.
      # class ListNode:
      #     def __init__(self, x):
      #         self.val = x
      #         self.next = None
    
      class Solution:
          # @param {ListNode} head
          # @return {ListNode}
          def reverseList(self, head):
              if head == None or head.next == None:
                  return head
              pre = head
              cur = pre.next
              pre.next = None
              while cur != None:
                  nex = cur.next
                  cur.next = pre
                  pre = cur
                  cur = nex
              return pre
    

##92. Reverse Linked List II

  • 难度:Medium

  • 题目大意:
    翻转链表中第 m 到 n 个元素。要求就地翻转,且一次遍历完成。给定的 m 和 n 总是合理的。

  • 思路:
    既然要求一次遍历完成,那就不能确定 m,n 位置然后调用上一题翻转链表函数来完成。那么我们可以从第 m 个节点开始,翻转 n-m+1 个节点结束。

  • 代码:

      class Solution2:
          # @param {ListNode} head
          # @param {integer} m
          # @param {integer} n
          # @return {ListNode}
          def reverseBetween(self, head, m, n):
              if head == None or head.next == None or m == n:
                  return head
              h,h.next = ListNode(-1),head
              pre,cur = h,h.next
              i = 0
              while i<=n:
                  if m<=i<n:
                      nex = cur.next
                      cur.next = pre
                      pre = cur
                      cur = nex
                  elif i==n:
                      p1.next = pre
                      p2.next = cur
                  else:
                      ##记录重要节点,用于拼装翻转和非翻转部分
                      if i==m-1:   
                          p1,p2 = pre,cur
                      pre = cur
                      cur = cur.next
                  i+=1
              return h.next
    

##24. Swap Nodes in Pairs

  • 难度:Medium

  • 题目大意:
    将链表中的节点两两互换。注意只能使用常数级空间,不能修改节点的值,只能使用原节点。

  • 思路:
    常规思路,就是做节点交换,每次推进两步,注意别越界。加入头结点,使第一个节点不用特殊处理。

  • 代码:

      # Definition for singly-linked list.
      # class ListNode:
      #     def __init__(self, x):
      #         self.val = x
      #         self.next = None
    
      class Solution:
          # @param {ListNode} head
          # @return {ListNode}
          def swapPairs(self, head):
              if not (head and head.next):
                  return head
              h = ListNode(0)
              h.next = head
              c,n = h,head
              while n and n.next:
                  c.next = n.next
                  c = c.next
                  n.next = c.next
                  c.next = n
                  c = n
                  n = n.next
              return h.next
    

##25. Reverse Nodes in k-Group

  • 难度:Hard

  • 题目大意:
    给定一个链表,以 k 个为一组进把链表逆序。不允许改变节点值,值运行使用常数空间。

  • 思路:
    这道题是 Swap Nodes in Pairs 的扩展版,还是常规思路就能解决,需要注意的是最后 n 个节点小于 k 时,不需要逆序。为了方便操作,我们把 k 个节点放入列表中,然后从后往前连接 next 指针。

  • 代码:

      # Definition for singly-linked list.
      # class ListNode:
      #     def __init__(self, x):
      #         self.val = x
      #         self.next = None
    
      class Solution:
          # @param {ListNode} head
          # @param {integer} k
          # @return {ListNode}
          def reverseKGroup(self, head, k):
              if k == 1:
                  return head
              h = ListNode(0)
              h.next = head
              c = h
              it = head
              buffer = []
              while c:
                  f = 0
                  buffer = []
                  for i in range(k):
                      if it:
                          buffer.append(it)
                          it = it.next
                      else:
                          f = 1
                          break
                  if len(buffer) == k:
                      for i in range(k-1):
                          buffer[i+1].next = buffer[i]
                  if f:
                      if buffer:
                          c.next = buffer[0]
                      c = None
                  else:
                      c.next = buffer[-1]
                      c = buffer[0]
                      c.next = None
              return h.next
    


#合并链表

##2.Add Two Numbers

  • 难度:Medium

  • 题目大意:
    给定两个由链表表示的非负数字。链表中每个节点包含一个数字,数字逆序排列(地位在前,高位在后),求两个数字之合,并以相同的链表格式返回。

  • 思路:
    这道题是一道简单的链表题,注意处理好进位,特别是最高位的进位即可。这道题本质上与合并链表思想是一致的,不过合并的是值而不是节点。

  • 代码:

      # Definition for singly-linked list.
      # class ListNode:
      #     def __init__(self, x):
      #         self.val = x
      #         self.next = None
    
      class Solution:
          # @param {ListNode} l1
          # @param {ListNode} l2
          # @return {ListNode}
          def addTwoNumbers(self, l1, l2):
              if not l1:
                  return l2
              if not l2:
                  return l1
              h1 = l1
              h2 = l2
              h3 = ListNode(-1)
              l3 = h3
              flag = 0
              while h1 or h2:
                  n1 = n2 = 0
                  if h1:
                      n1 = h1.val
                      h1 = h1.next
                  if h2:
                      n2 = h2.val
                      h2 = h2.next
                  node = ListNode((n1+n2+flag)%10)
                  if n1+n2+flag >= 10:
                      flag = 1
                  else:
                      flag = 0
                  h3.next = node
                  h3 = h3.next
              if flag == 1:
                  node = ListNode(1)
                  h3.next = node
              return l3.next
    

##21.Merge Two Sorted Lists

  • 难度:Easy

  • 题目大意:
    将两个已排序的链表合并,注意,合并后的链表必须使用原来节点。

  • 思路:
    没有什么特殊的,常规思路:比较两个链表的第一个节点,取小的加入新链表,然后推进。注意头结点的特殊处理,及注意别访问越界空间即可。

  • 代码:

      # Definition for singly-linked list.
      # class ListNode:
      #     def __init__(self, x):
      #         self.val = x
      #         self.next = None
    
      class Solution:
          # @param {ListNode} l1
          # @param {ListNode} l2
          # @return {ListNode}
          def mergeTwoLists(self, l1, l2):
              if not l1:return l2
              if not l2:return l1
              l1c,l2c = l1,l2
              l1n,l2n = l1.next,l2.next
              if l1c.val <= l2c.val:
                  head = l1c
                  l1c = l1n
                  if l1n:
                      l1n = l1n.next
              else:
                  head = l2c
                  l2c = l2n
                  if l2n:
                      l2n = l2n.next
              c = head
              while l1c or l2c:
                  if l1c and l2c:
                      if l1c.val<=l2c.val:
                          c.next = l1c
                          c = c.next
                          l1c = l1n
                          if l1n:
                              l1n = l1n.next
                      else:
                          c.next = l2c
                          c =c.next
                          l2c = l2n
                          if l2n:
                              l2n = l2n.next
                  elif l1c:
                      c.next = l1c
                      break
                  elif l2c:
                      c.next = l2c
                      break
    
              return head
    

##23. Merge k Sorted Lists

  • 难度:Hard
  • 题目大意:
    将 K 个已排序的列表合并,注意复杂度。
  • 思路:
    这道题是合并 2 个列表的升级版,难度立马提升到 Hard 级别。很明显我们不能像合并 2 个两边那样,比较 k 个链表的第一个节点,然后选取最小的然后推进,这样子情况太过复杂。打破最常规的思路,我们能想到的思路就比较多了。
  1. 我们可以把所有的节点放入数组中,然后根据节点的 val 进行排序,最后再把节点串起来即可。这种做法实现非常简单,但是这种做法浪费了原来各个链表已经排好序这样一个条件,会使复杂度增加。
  2. 创建一个大小为 k 的堆,把 k 个链表的头节点 push 进去。每次从堆中 pop 出最小的节点,若该节点有 next 则加入堆中。直到堆为空。注意,若不能提供自定义排序,每次 push 进堆(val,node)这样的元组就会方便得多。事实上,这道题考察的真是我们对堆这种数据结构的理解。
  3. 分治,将问题变成合并两个已排序链表的问题。这种方法实现细节比较多,这里就不写了。
  • 代码:

      # Definition for singly-linked list.
      # class ListNode:
      #     def __init__(self, x):
      #         self.val = x
      #         self.next = None
    
      class Solution1:
          # @param {ListNode[]} lists
          # @return {ListNode}
          def mergeKLists(self, lists):
              nodes = []
              for l in lists:
                  while l:
                      nodes.append(l)
                      l = l.next
              if not nodes:
                  return
              nodes.sort(key=lambda node:node.val)
              for i in range(len(nodes)-1):
                  nodes[i].next = nodes[i+1]
              nodes[-1].next = None
              return nodes[0]
    
    
      class Solution2:
          # @param {ListNode[]} lists
          # @return {ListNode}
          def mergeKLists(self, lists):
              import heapq
              head=p=ListNode(-1)
              h = []
              for node in lists:
                  if node: heapq.heappush(h,(node.val,node))
              while h:
                  curlist = heapq.heappop(h)[1]
                  p.next = curlist
                  p = p.next
                  if curlist.next:
                      heapq.heappush(h,(curlist.next.val,curlist.next))
              return head.next
    


#改变节点顺序
此类型包括排序和其他按照题目要求改变节点相对顺序的题目。

##61. Rotate List

  • 难度:Medium

  • 题目大意:
    给定一个链表,将右侧 k 个节点翻转到左侧,k 为非负数。

  • 思路:
    这道题有两种思路,一种是用两个指针,两个指针之间保持间隔为 k,当第二个指针指向尾部时,第一个指针就是需要断开的地方。另一种是把节点放在列表中,这样从哪里断开就一目了然了,重新连起链表就可以了。
    需要注意几种特殊情况,若 k 大于链表长度,k=0,k=链表长度。
    题目虽然为 rotate,然而和翻转并没有关系。

  • 代码:

      # Definition for singly-linked list.
      # class ListNode:
      #     def __init__(self, x):
      #         self.val = x
      #         self.next = None
    
      class Solution:
          # @param {ListNode} head
          # @param {integer} k
          # @return {ListNode}
          def rotateRight(self, head, k):
              nodes = []
              while head:
                  nodes.append(head)
                  head = head.next
              if nodes:
                  k%=len(nodes)
              left = nodes[:len(nodes)-k]
              right = nodes[len(nodes)-k:]
              if right and left:
                  right[-1].next = left[0]
                  left[-1].next=None
                  return right[0]
              elif right and not left:
                  right[-1].next=None
                  return right[0]
              elif left and not right:
                  left[-1].next=None
                  return left[0]
              else:
                  return head
    

##86. Partition List

  • 难度: Medium

  • 题目大意:
    给定一个链表和值 x,对链表进行调整,使值小于 x 的节点在值大于等于 x 的节点的左边。

  • 思路:
    这道题乍一看好像挺难,但其实很简单。题目表述的这个过程不就是快排的一趟调整嘛,只是变成链表操作而已。当初使用链表操作会比较麻烦,要记录前驱什么的比较麻烦。但是如果把链表的节点放到列表中(我很喜欢这么做!),那不就是和快排一模一样。不懂快排?没关系,说一下就懂。用 i 记录小于 x 区域的右侧(第一个大于等于 x 的数)位置,j 向前探索,若发现比 x 小的值,则和 i 位置进行交换,并把 i+1。

  • 代码:

      class ListNode:
          def __init__(self, x):
              self.val = x
              self.next = None
    
      class Solution:
          # @param {ListNode} head
          # @param {integer} x
          # @return {ListNode}
          def partition(self, head, x):
              if not head:
                  return head
              nodes = []
              while head:
                  nodes.append(head)
                  head = head.next
              i=j=0
              while j<len(nodes):
                  if nodes[j].val < x:
                      node = nodes.pop(j)
                      nodes.insert(i,node)
                      i += 1
                  j += 1
              for i in range(len(nodes)-1):
                  print(nodes[i].val)
                  nodes[i].next = nodes[i+1]
              nodes[-1].next = None
              return nodes[0]
    

##143. Reorder List

  • 难度:Medium

  • 题目大意:
    给定一个链表,原来的序列是 L0,L1 ,...Ln-1,Ln,要求改变为 L0,Ln,L1,Ln-1,L2,Ln-2...。只能使用常数级空间,不可改变节点的值。

  • 思路:
    如果给定的不是一个链表而是一个数组就好了,因为我们需要定位到最后 1 个节点,且往前移动。对单链表来说,往前移动是不可能的。确实可以变成数组,我最喜欢干这样的事情。但是有个问题就是,每次插入都要使后面的节点往后移动,这也是数组比链表差的地方。这次我们不使用这么 low 的方法。我们可以把问题拆分为,找链表中点,切割成两个链表,对后面那个链表原地翻转,再将两个链表合并,啊哈这是一道综合题啊。

  • 代码:

      # Definition for singly-linked list.
      # class ListNode:
      #     def __init__(self, x):
      #         self.val = x
      #         self.next = No
      class Solution:
          # @param {ListNode} head
          # @return {void} Do not return anything, modify head in-place instead.
          def reorderList(self, head):
              if not head or not head.next:return
              s1,s2=head,head
              ##cut
              while s2 and s2.next:
                  s1,s2=s1.next,s2.next.next
              head2 = s1.next
              s1.next=None
              ##reverse
              head2 = self.reverseList(head2)
              ##merge
              while head2:
                  p1=head.next
                  head.next=head2
                  head=p1
                  p2=head2.next
                  head2.next=head
                  head2=p2
    
    
          ##206 Reverse Linked List
          def reverseList(self, head):
              if head == None or head.next == None:
                  return head
              pre = head
              cur = pre.next
              pre.next = None
              while cur != None:
                  nex = cur.next
                  cur.next = pre
                  pre = cur
                  cur = nex
              return pre
    

##147. Insertion Sort List

  • 难度:Medium

  • 题目大意:
    使用插入排序的方法对一个链表进行排序。

  • 思路:
    没什么好说的,人家已经把思路写在题目上了,就是要用插入排序

  • 代码:

      # Definition for singly-linked list.
      # class ListNode:
      #     def __init__(self, x):
      #         self.val = x
      #         self.next = None
    
      class Solution:
          # @param head, a ListNode
          # @return a ListNode
          def insertionSortList(self, head):
              if head == None or head.next == None:
                  return head
              h = ListNode(0)
              h.next = head
              cur = head
              while cur.next:
                  if cur.next.val < cur.val:
                      pre = h
                      while pre.next.val < cur.next.val:
                          pre = pre.next
                      temp = cur.next
                      cur.next = temp.next
                      temp.next = pre.next
                      pre.next = temp
                  else:
                      cur = cur.next
              return h.next
    

##148. Sort List

  • 难度:Medium

  • 题目大意:
    使用 O(n log n)时间复杂度和常数级空间复杂度对链表进行排序。

  • 思路:
    这回人家不告诉我们怎么做了。时间复杂度为 O(nlogn)的排序算法也就那么几个,结合链表的实际情况,我们采用合并排序,原因很简单,合并时空复杂度均符合,且我们之前已经写了大量的把链表切分成 2 半,合并链表的代码,拿过来就可以直接用了。

  • 代码:

      # Definition for singly-linked list.
      # class ListNode:
      #     def __init__(self, x):
      #         self.val = x
      #         self.next = None
    
      class Solution:
          # @param {ListNode} head
          # @return {ListNode}
          def sortList(self, head):
              if not head or not head.next:return head
              head2=self.cutList(head)
              return self.mergeTwoLists(self.sortList(head),self.sortList(head2))
    
          def cutList(self,head):
              s1,s2=head,head
              while s2.next and s2.next.next:
                  s1,s2=s1.next,s2.next.next
              head2 = s1.next
              s1.next=None
              return head2
    
          def mergeTwoLists(self, l1, l2):
              if not l1:return l2
              if not l2:return l1
              l1c,l2c = l1,l2
              l1n,l2n = l1.next,l2.next
              if l1c.val <= l2c.val:
                  head = l1c
                  l1c = l1n
                  if l1n:
                      l1n = l1n.next
              else:
                  head = l2c
                  l2c = l2n
                  if l2n:
                      l2n = l2n.next
              c = head
              while l1c or l2c:
                  if l1c and l2c:
                      if l1c.val<=l2c.val:
                          c.next = l1c
                          c = c.next
                          l1c = l1n
                          if l1n:
                              l1n = l1n.next
                      else:
                          c.next = l2c
                          c =c.next
                          l2c = l2n
                          if l2n:
                              l2n = l2n.next
                  elif l1c:
                      c.next = l1c
                      break
                  elif l2c:
                      c.next = l2c
                      break
              return head
    

##328. Odd Even Linked List

  • 难度:Easy

  • 题目大意:
    将给定列表进行重组,使奇数节点在前偶数节点在后(这里指的是序数而不是节点的值),奇数节点(偶数节点)的相对位置不发生改变。要求就地解决,使用 O(1)空间 O(n)时间解决。

  • 思路:
    想法直接而简单,node.next=node.next.next,最后首尾相连。注意不要访问越界即可。

  • 代码:

      # Definition for singly-linked list.
      # class ListNode(object):
      #     def __init__(self, x):
      #         self.val = x
      #         self.next = None
    
      class Solution(object):
          def oddEvenList(self, head):
              """
              :type head: ListNode
              :rtype: ListNode
              """
              if not head or not head.next:return head
              h1=c1=head
              h2=c2=head.next
    
              while True:
                  if not c1.next or not c1.next.next:
                      break
                  c1.next=c1.next.next
                  c1=c1.next
                  c2.next=c2.next.next
                  c2=c2.next
              c1.next=h2
              if c2:
                  c2.next=None
              return h1;
    

#环

##141. Linked List Cycle

  • 难度:Medium

  • 题目大意:
    给定一个链表,检测其是否含有环

  • 思路:
    烂大街的面试题,必须会。使用两个指针,一个每次推进 1 步,另一个每次推进 2 步,若存在环,这两个指针必相遇。为什么快指针不每次走 3 步或更多,因为快指针可能跨过慢指针而不相遇。

  • 代码:

      class Solution:
          # @param head, a ListNode
          # @return a boolean
          def hasCycle(self, head):
              s1,s2=head,head
              while s1 and s2 and s2.next:
                  s1,s2 = s1.next,s2.next.next
                  if s1 == s2:
                      return True
              return False
    

##142. Linked List Cycle II

  • 难度:Medium

  • 题目大意:
    给定一个链表,若存在环,求环的入口,若不存在返回 null。

  • 思路:
    求环的升级问题,问了上面那个问题,肯定会追加这个问题的。这个问题需要进行简单的数学求证,假设环之前的路程为 a,相遇点离环入口 x,慢指针走的路程为 s,环长度为 c,则存在以下关系:2s-s=nc (快指针比慢指针多走了 n 圈) s=a+x。两公式推导出:a=(n-1)c+c-x。则有若两个指针,一个从起点出发,另一个从相遇点出发,均每次推进 1 步,则他们会在环入口处相遇。

  • 代码:

      class Solution:
          # @param head, a ListNode
          # @return a list node
          def detectCycle(self, head):
              s1 = self.hasCycle(head)
              if s1:
                  while s1 and head:
                      if s1==head:
                          return head
                      s1,head=s1.next,head.next
              return None
    
          def hasCycle(self,head):
              s1,s2=head,head
              while s1 and s2 and s2.next:
                  s1,s2 = s1.next,s2.next.next
                  if s1 == s2:
                      return s1
              return None
    


#综合及其他问题

##109. Convert Sorted List to Binary Search Tree (链表和树)

  • 难度:Medium

  • 题目大意:
    给定一个升序链表,将链表变成高度平衡二叉查找树。

  • 思路:
    这道题其实就和链表没有什么关系了(就算有关系,我也会把节点放到列表里),主要考察的是平衡二叉查找数的概念。由于要求高度平衡,因此,我们肯定总是需要查找中位数,虽然链表已经排序好了,但是要查中间的节点总是需要扫一遍很不方便,因此我们把节点发到列表中(看,和链表没关系了把!)。二叉查找数的定义是一个递归的过程, 因为每个节点的左子树和右子树都是二叉查找数,由于平衡,所以父节点总是左子树和右子树的中位数。

  • 代码:

      # Definition for singly-linked list.
      # class ListNode:
      #     def __init__(self, x):
      #         self.val = x
      #         self.next = None
    
      # Definition for a binary tree node.
      # class TreeNode:
      #     def __init__(self, x):
      #         self.val = x
      #         self.left = None
      #         self.right = None
    
      class Solution:
          # @param {ListNode} head
          # @return {TreeNode}
          def sortedListToBST(self, head):
              nums = []
              while head:
                  nums.append(head.val)
                  head = head.next
              return self.sortedArrayToBST(nums)
    
    
          def sortedArrayToBST(self, nums):
              if not nums: return None
              mid = len(nums)//2
              root = TreeNode(nums[mid])
              root.left = self.sortedArrayToBST(nums[:mid])
              root.right = self.sortedArrayToBST(nums[mid+1:])
              return root
    

##138. Copy List with Random Pointer (深度拷贝)

  • 难度:Hard

  • 题目大意:
    给定一个链表,每个节点有一个额外的指针,指向任意链表中的节点或空。返回该链表的深度拷贝。

  • 思路:
    这道题的难度在于,额外的随机指针,当你复制该节点时,若随机指针指向前面的节点,如何找到,若指向后面的节点,如何处理。我这里采用一种神奇的办法。复制节点的同时,把新节点插入到被复制节点的后面,随机指针暂时跟被复制节点保持一致。这样一遍下来,我们构造的新链表由旧节点和对应的新节点构成。再遍历一遍,我们只需要把新节点的随机指针该为其指向的节点的 next 即可(其指向的节点为旧节点,旧节点的 next 是其对应的新节点)。最后遍历一遍,把新节点的 next 链接起来即可。

  • 代码:

      # Definition for singly-linked list with a random pointer.
      # class RandomListNode(object):
      #     def __init__(self, x):
      #         self.label = x
      #         self.next = None
      #         self.random = None
    
      class Solution(object):
          def copyRandomList(self, head):
              """
              :type head: RandomListNode
              :rtype: RandomListNode
              """
              if not head:return head
              node=head
              while node:
                  copyNode = RandomListNode(node.label)
                  copyNode.random = node.random
                  copyNode.next = node.next
                  node.next = copyNode
                  node = node.next.next
    
              node=head
              while node:
                  if node.random:
                      node.next.random = node.random.next
                  node = node.next.next
    
              phead=RandomListNode(0)
              phead.next=head
              newlist=phead
              node=head
    
              while node:
                  phead.next=node.next
                  node.next=phead.next.next
                  phead=phead.next
                  node=node.next
              return newlist.next
    
  • 思路 2:前面那种方法需要遍历 3 次链表,且改变了原来的数据结构,而且非常难想到那一种解决办法。我们上面分析了,这道题的难点在于判断随机指针指向的节点。那么我们可以考虑用哈希表进行存储节点和查询,键是旧链表节点,值是对应的新链表节点。我们第一次遍历复制每个节点,next 指针和随机指针暂时不管。第二次遍历以旧链表节点为键查找新的 next 指针和随机链表的指向。代码简洁大方,哈哈哈。

      class Solution(object):
          def copyRandomList(self, head):
              if not head:return head
              nodes={None:None}
              cur = head
              while cur:
                  newCur = RandomListNode(cur.label)
                  nodes[cur]=newCur
                  cur = cur.next
              cur = head
              while cur:
                  nodes[cur].next = nodes[cur.next]
                  nodes[cur].random = nodes[cur.random]
                  cur = cur.next
              return nodes[head]
    

##160. Intersection of Two Linked Lists(公共节点)

  • 难度:Easy

  • 题目大意:
    找到两个链表公共节点的开始节点。

  • 思路:
    也是烂大街的面试题。先求两个链表的长度 n,m,然后再用两个指针遍历,长链表指针先行 abs(n-m),然后两个指针同时走,若指针指向同一节点,则该节点为公共节点的开始。

  • 代码:

      # Definition for singly-linked list.
      # class ListNode:
      #     def __init__(self, x):
      #         self.val = x
      #         self.next = None
    
      class Solution:
          # @param two ListNodes
          # @return the intersected ListNode
          def getIntersectionNode(self, headA, headB):
              if not headA or not headB:return None
              la=lb=1
              ha,hb=headA,headB
              while ha.next:
                  ha=ha.next
                  la+=1
              while hb.next:
                  hb=hb.next
                  lb+=1
              if ha!=hb:return None
              if la>=lb:
                  i=0
                  for i in range(la-lb):
                      headA=headA.next
              else:
                  i=0
                  for i in range(lb-la):
                      headB=headB.next
              while headA!=headB:
                  headA=headA.next
                  headB=headB.next
              return headA
    

##234. Palindrome Linked List (回文链表)

  • 难度:Easy

  • 题目大意:
    给定一个链表,判断是否为回文。在 O(n)时间,O(1)空间内完成。

  • 思路:
    唉,如果是字符串或者是数组就好判断了。啊哈,这里又要祭出赖皮招式了,把节点放入列表中(这是 py 最方便的地方,列表可以容纳一切),这样就能达到顺序和随机访问了。

  • 代码:

      # Definition for singly-linked list.
      # class ListNode(object):
      #     def __init__(self, x):
      #         self.val = x
      #         self.next = None
    
      class Solution(object):
          def isPalindrome(self, head):
              """
              :type head: ListNode
              :rtype: bool
              """
              stack=[]
              while head:
                  stack.append(head)
                  head=head.next
              i,j=0,len(stack)-1
              while i<=j:
                  if stack[i].val!=stack[j].val:
                      return False
                  i,j=i+1,j-1
              return True
    

  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    209 引用 • 72 回帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • 钉钉

    钉钉,专为中国企业打造的免费沟通协同多端平台, 阿里巴巴出品。

    15 引用 • 67 回帖 • 381 关注
  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    209 引用 • 72 回帖
  • 七牛云

    七牛云是国内领先的企业级公有云服务商,致力于打造以数据为核心的场景化 PaaS 服务。围绕富媒体场景,七牛先后推出了对象存储,融合 CDN 加速,数据通用处理,内容反垃圾服务,以及直播云服务等。

    25 引用 • 215 回帖 • 160 关注
  • Sandbox

    如果帖子标签含有 Sandbox ,则该帖子会被视为“测试帖”,主要用于测试社区功能,排查 bug 等,该标签下内容不定期进行清理。

    362 引用 • 1212 回帖 • 580 关注
  • 酷鸟浏览器

    安全 · 稳定 · 快速
    为跨境从业人员提供专业的跨境浏览器

    3 引用 • 59 回帖 • 21 关注
  • 安全

    安全永远都不是一个小问题。

    189 引用 • 813 回帖 • 2 关注
  • 百度

    百度(Nasdaq:BIDU)是全球最大的中文搜索引擎、最大的中文网站。2000 年 1 月由李彦宏创立于北京中关村,致力于向人们提供“简单,可依赖”的信息获取方式。“百度”二字源于中国宋朝词人辛弃疾的《青玉案·元夕》词句“众里寻他千百度”,象征着百度对中文信息检索技术的执著追求。

    63 引用 • 785 回帖 • 249 关注
  • 微信

    腾讯公司 2011 年 1 月 21 日推出的一款手机通讯软件。用户可以通过摇一摇、搜索号码、扫描二维码等添加好友和关注公众平台,同时可以将自己看到的精彩内容分享到微信朋友圈。

    129 引用 • 793 回帖 • 1 关注
  • 思源笔记

    思源笔记是一款隐私优先的个人知识管理系统,支持完全离线使用,同时也支持端到端加密同步。

    融合块、大纲和双向链接,重构你的思维。

    18150 引用 • 66978 回帖
  • Caddy

    Caddy 是一款默认自动启用 HTTPS 的 HTTP/2 Web 服务器。

    10 引用 • 54 回帖 • 126 关注
  • TextBundle

    TextBundle 文件格式旨在应用程序之间交换 Markdown 或 Fountain 之类的纯文本文件时,提供更无缝的用户体验。

    1 引用 • 2 回帖 • 45 关注
  • CAP

    CAP 指的是在一个分布式系统中, Consistency(一致性)、 Availability(可用性)、Partition tolerance(分区容错性),三者不可兼得。

    11 引用 • 5 回帖 • 552 关注
  • 持续集成

    持续集成(Continuous Integration)是一种软件开发实践,即团队开发成员经常集成他们的工作,通过每个成员每天至少集成一次,也就意味着每天可能会发生多次集成。每次集成都通过自动化的构建(包括编译,发布,自动化测试)来验证,从而尽早地发现集成错误。

    14 引用 • 7 回帖
  • DevOps

    DevOps(Development 和 Operations 的组合词)是一组过程、方法与系统的统称,用于促进开发(应用程序/软件工程)、技术运营和质量保障(QA)部门之间的沟通、协作与整合。

    37 引用 • 24 回帖 • 1 关注
  • Wide

    Wide 是一款基于 Web 的 Go 语言 IDE。通过浏览器就可以进行 Go 开发,并有代码自动完成、查看表达式、编译反馈、Lint、实时结果输出等功能。

    欢迎访问我们运维的实例: https://wide.b3log.org

    30 引用 • 218 回帖 • 594 关注
  • Ubuntu

    Ubuntu(友帮拓、优般图、乌班图)是一个以桌面应用为主的 Linux 操作系统,其名称来自非洲南部祖鲁语或豪萨语的“ubuntu”一词,意思是“人性”、“我的存在是因为大家的存在”,是非洲传统的一种价值观,类似华人社会的“仁爱”思想。Ubuntu 的目标在于为一般用户提供一个最新的、同时又相当稳定的主要由自由软件构建而成的操作系统。

    123 引用 • 168 回帖
  • RIP

    愿逝者安息!

    8 引用 • 92 回帖 • 284 关注
  • Angular

    AngularAngularJS 的新版本。

    26 引用 • 66 回帖 • 498 关注
  • LaTeX

    LaTeX(音译“拉泰赫”)是一种基于 ΤΕΧ 的排版系统,由美国计算机学家莱斯利·兰伯特(Leslie Lamport)在 20 世纪 80 年代初期开发,利用这种格式,即使使用者没有排版和程序设计的知识也可以充分发挥由 TeX 所提供的强大功能,能在几天,甚至几小时内生成很多具有书籍质量的印刷品。对于生成复杂表格和数学公式,这一点表现得尤为突出。因此它非常适用于生成高印刷质量的科技和数学类文档。

    9 引用 • 32 回帖 • 178 关注
  • Vue.js

    Vue.js(读音 /vju ː/,类似于 view)是一个构建数据驱动的 Web 界面库。Vue.js 的目标是通过尽可能简单的 API 实现响应的数据绑定和组合的视图组件。

    261 引用 • 662 回帖 • 1 关注
  • 禅道

    禅道是一款国产的开源项目管理软件,她的核心管理思想基于敏捷方法 scrum,内置了产品管理和项目管理,同时又根据国内研发现状补充了测试管理、计划管理、发布管理、文档管理、事务管理等功能,在一个软件中就可以将软件研发中的需求、任务、bug、用例、计划、发布等要素有序的跟踪管理起来,完整地覆盖了项目管理的核心流程。

    5 引用 • 15 回帖 • 223 关注
  • Unity

    Unity 是由 Unity Technologies 开发的一个让开发者可以轻松创建诸如 2D、3D 多平台的综合型游戏开发工具,是一个全面整合的专业游戏引擎。

    25 引用 • 7 回帖 • 248 关注
  • HHKB

    HHKB 是富士通的 Happy Hacking 系列电容键盘。电容键盘即无接点静电电容式键盘(Capacitive Keyboard)。

    5 引用 • 74 回帖 • 402 关注
  • FreeMarker

    FreeMarker 是一款好用且功能强大的 Java 模版引擎。

    23 引用 • 20 回帖 • 427 关注
  • 微软

    微软是一家美国跨国科技公司,也是世界 PC 软件开发的先导,由比尔·盖茨与保罗·艾伦创办于 1975 年,公司总部设立在华盛顿州的雷德蒙德(Redmond,邻近西雅图)。以研发、制造、授权和提供广泛的电脑软件服务业务为主。

    8 引用 • 44 回帖
  • 知乎

    知乎是网络问答社区,连接各行各业的用户。用户分享着彼此的知识、经验和见解,为中文互联网源源不断地提供多种多样的信息。

    10 引用 • 66 回帖
  • jsDelivr

    jsDelivr 是一个开源的 CDN 服务,可为 npm 包、GitHub 仓库提供免费、快速并且可靠的全球 CDN 加速服务。

    5 引用 • 31 回帖 • 33 关注