问题描述
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
解题思路
添加一个虚拟头结点，然后使用头插法构建链表。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | # Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
vhead = ListNode(0)
cur = head
while cur:
nxt = cur.next
cur.next = vhead.next
vhead.next = cur
cur = nxt
return vhead.next
|
1-->2-->3-->4-->5 假设 2-->3-->4-->5 已经反转好了变为了 5-->4-->3-->2。
而 1 最开始是指向 2，所以此时只要设置 2.next = 1 和 1.next = None。
- 即
1.next.next = 1
1.next = None
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | # Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
rest_head = self.reverseList(head.next)
head.next.next = head
head.next = None
return rest_head
|