题目描述
206. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
1
2
| 输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
|
示例 2：
1
2
| 输入：head = [1,2]
输出：[2,1]
|
示例 3：
提示：
- 链表中节点的数目范围是
[0, 5000]
-5000 <= Node.val <= 5000
解题思路
假设链表为 1→2→3→∅，我们想要把它改成 ∅←1←2←3。
在遍历链表时，将当前节点的 next指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。
代码实现
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
| public class Solution206Case1 {
public static ListNode reverseList(ListNode head) {
if (null == head || null == head.next) {
return head;
}
List<ListNode> nodes = new ArrayList<>();
ListNode temp = head;
while (temp != null) {
ListNode listNode = new ListNode(temp.val);
nodes.add(listNode);
temp = temp.next;
}
for (int i = nodes.size() - 1; i > 0; i--) {
nodes.get(i).next = nodes.get(i - 1);
}
return nodes.get(nodes.size() - 1);
}
public static void main(String[] args) {
ListNode node5 = new ListNode(5);
ListNode node4 = new ListNode(4, node5);
ListNode node3 = new ListNode(3, node4);
ListNode node2 = new ListNode(2, node3);
ListNode node1 = new ListNode(1, node2);
ListNode listNode = reverseList(node1);
System.err.println(listNode);
}
}
|
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
| public class Solution206 {
public static ListNode reverseList(ListNode head) {
if (null == head || null == head.next) {
return head;
}
List<ListNode> nodes = new ArrayList<>();
ListNode temp = head;
while (temp != null) {
ListNode listNode = new ListNode(temp.val);
nodes.add(listNode);
temp = temp.next;
}
for (int i = nodes.size() - 1; i > 0; i--) {
nodes.get(i).next = nodes.get(i - 1);
}
return nodes.get(nodes.size() - 1);
}
public static void main(String[] args) {
ListNode node5 = new ListNode(5);
ListNode node4 = new ListNode(4, node5);
ListNode node3 = new ListNode(3, node4);
ListNode node2 = new ListNode(2, node3);
ListNode node1 = new ListNode(1, node2);
ListNode listNode = reverseList(node1);
System.err.println(listNode);
}
}
|