LeetCode 206. Reverse Linked List

题目

Reverse a singly linked list.

分析

翻转一个链表

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
# iteratively
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
dummy = ListNode(-1)
while head:
tmp = head
head = head.next
tmp.next = dummy.next
dummy.next = tmp
return dummy.next
# recursively
def reverseList1(self, head):
return self._reverse(head)
def _reverse(self, node, prev=None):
if not node:
return prev
n = node.next
node.next = prev
return self._reverse(n, node)

点评

翻转一个链表
迭代方式比较好理解,首先申请一个空的头结点,然后开始遍历链表,每次遍历的时候,将遍历的那个节点插入 dummy 节点之后
递归方式这里比较巧妙,每次递归时,传递的信息是当前节点和上一个节点,如果当前节点为空,那么直接返回上一个节点,每次递归时也是直接返回下一次递归的结果,但是每次递归的时候,都会把当前节点和上一个节点的顺序对调,简直巧妙!

这里可以看出递归程序的四个关键点:

  • 每次递归传递的什么信息
  • 递归的结束条件是什么,返回的什么值
  • 每次递归的时候怎么处理返回值的
  • 每次递归干了什么