206. 反转链表

题目

最简单的思路是遍历链表一个列表去做存储，通过倒序读取列表的同时改写链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
  def reverseList(self, head):
    if not head or not head.next:
      return head
    nl = []
    while head.next:
      nl.append(head)
      head = head.next
    nl.append(head)
    l = len(nl)
    for x in range(l):
      if x == 0:
        nl[x].next = None
        continue
      nl[x].next = nl[x-1]
      if x == (l - 1):
        return nl[x]

仔细想想自己又傻逼了，何必要遍历两次呢，在第一遍遍历的同时就能操作了：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
  def reverseList(self, head):
    if not head or not head.next:
      return head
    prev_node = None
    next_node = head.next
    while head:
      next_node = head.next
      head.next = prev_node
      prev_node = head
      head = next_node
    return prev_node

然后是递归的做法，主要思路是一直进到最深一层–也就是链表的最后一个–的时候开始返回，同时修改那一层的两个 node。一开始踩了一个坑是返回了每一个node，结果最后回到第一层的时候得到的是链表的末端，其实只需要修改链表，并不需要返回 node，所以一开始到达链表末端的时候直接返回那一个node就可以了。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
  def reverseList(self, head):
    if not head:
      return head
    if head.next:
      ss = Solution()
      last = ss.reverseList(head.next)
      head.next.next = head
      head.next = None
      return last
    return head

一开始是用list来打草稿，不过想明白递归之后就大同小异了：

1
2
3
4
5
6
7
8
9
def a(l:list)->list:
  k=[l[0]]

  if l[1:]:
    b=a(l[1:])
    b.extend(k)
  else:
    return [l[0]]
  return b