反转链表
力扣题号206 反转链表
题目描述：
1
| 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
|
1
2
3
4
5
6
7
8
| 输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
输入：head = [1,2]
输出：[2,1]
输入：head = []
输出：[]
|
这道题的解决方式有很多，最简单的就是在创建一个新的链表，逆序赋值，或者利用一个栈，但是这样属于外门邪道了，要求是不额外申请新的空间。
ListNode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
|
双指针法
双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public ListNode reverseList(ListNode head) {
ListNode temp;
ListNode cur = head;
ListNode pre = null;
while (cur != null){
temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
}
|
递归
递归法理解起来比较负责，不过反转的思路是和双指针一样的
递归法
1
2
3
4
5
6
7
8
9
10
11
12
13
| public ListNode reverseList(ListNode head) {
return reverse(null,head);
}
public ListNode reverse(ListNode pre,ListNode curr){
if (curr == null){
return pre;
}
ListNode temp = null;
temp = curr.next;
curr.next = pre;
return reverse(curr, temp);
}
|
