来源Leetcode第206题反转链表
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
初次提交
一开始做的时候直接想着把链表形成一个闭环，然后通过这个闭环从最后一个结点逐一找到前一个结点，提交后用时击败了5.75%的用户，在二重循环里浪费了太多的时间。
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
| public static ListNode reverseList(ListNode head) {
if(head == null || head.next == null)
return head;
ListNode p1 = head;
ListNode p2;
int len = 1;
while (p1.next != null) {
p1 = p1.next;
len++;
}
p1.next = head;
ListNode newHead = p1;
for(int i = 0;i < len; i ++){
p2 = p1;
for(;p2.next != p1;p2 = p2.next);
p2.next = head;
p1.next = p2;
if(p2.next.next == p2){
p2.next.next = null;
break;
}
p1 = p1.next;
}
return newHead;
}
|
迭代
在遍历列表时，将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点，因此必须事先存储其前一个元素。在更改引用之前，还需要另一个指针来存储下一个节点。
1
2
3
4
5
6
7
8
9
10
11
| public ListNode reverseList(ListNode head) {
ListNode p1 = null;
ListNode P2 = head;
while (P2 != null) {
ListNode nextTemp = P2.next;
P2.next = p1;
p1 = P2;
P2 = nextTemp;
}
return p1;
}
|
递归
来源题解
假设链表是[1, 2, 3, 4, 5]从最底层最后一个reverseList(5)来看
- 返回了5这个节点
- reverseList(4)中
- p为5
- head.next.next = head 相当于 5 -> 4
- 现在节点情况为 4 -> 5 -> 4
- head.next = null,切断4 -> 5 这一条，现在只有 5 -> 4
- 返回（return）p为5，5 -> 4
- 返回上一层reverseList(3)
- 处理完后返回的是4 -> 3
- 依次向上
1
2
3
4
5
6
7
| public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode p = reverseList(head.next);
head.next.next = head;
head.next = null;
return p;
}
|