leetcode-206-Reverse-Linked-List 反转链表
1. 题目
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
2. 解
2.1 方法一：借用栈结构反转
借用Python中list中的insert()函数实现栈结构，用栈来反转。
需要注意的是：整个过程中，不动head结点，新初始化一个结点p来遍历链表。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
p = head
newList = []
while p:
newList.insert(0,p.val)
p = p.next
p = head
for x in newList:
p.val = x
p = p.next
return head
2.2 方法二：迭代反转
其实就是头插法。
当怎么想都想不通的时候，其实是这里出问题了：
这里的链表是 1->2->3->4
最重要的是：head 就是 1 这个节点，head = 1
并不是 head -> 1 (head.next = 1) 这个是最致命的错误思路，不是head指向1，而是head就是1，head和1就是同一个节点，1 这个节点就是所谓的头结点
只要把head和1想成同一个节点，问题就都解决了
2.2.1 头插法一：
在链表中反转（head的后继结点插入链表头）
head遍历链表。t为head的后继结点，反转操作主要是：
head指向head.next.next（即为t.next，把t摘下来），t插入链表头（t.next = new_head），重置头结点（new_head = t）1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None:
return head
# new_head保存链表头，head遍历链表
new_head = head
while head.next is not None:
t = head.next
head.next = head.next.next
t.next = new_head
new_head = t
return new_head
2.2.2 头插法二：
链表拆分为两条（head的前序结点插入链表头）
head遍历链表，p为head的前序结点，反转操作主要是：
将前序结点p直接插在新链表new_head之前（p.next = new_head），重新将new_head指向头结点（new_head = p）。
1 | # Definition for singly-linked list. |
2.3 方法三：递归
1 | # Definition for singly-linked list. |