0%

Algorithm_链表反转

Define ListNode

1
2
3
4
5
6
7
8
9
public class ListNode {
int val;
ListNode next;

ListNode(int x) {
val = x;
next = null;
}
}
  1. 使用栈Stack的方式来实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public ListNode reverseList(ListNode head) {

Stack<ListNode> stack = new Stack<>();

if (head == null) {
return null;
}

ListNode cur = head;
while (cur != null) {
stack.push(new ListNode(cur.val));
cur = cur.next;
}

cur = stack.pop();
ListNode newListNode = cur;
while (!stack.isEmpty()) {
cur.next = stack.pop();
cur = cur.next;
}
return newListNode;
}
  1. 双指针的方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public ListNode reverseList(ListNode head) {

if (head == null || head.next == null) {
return head;
}

ListNode pre = null;
ListNode cur = head;
ListNode next = null;

while (cur != null) {
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
  1. 递归的方式
1
2
3
4
5
6
7
8
9
10
11
public ListNode reverseList(ListNode head) {

if (head == null || head.next == null) {
return head;
}

ListNode listNode = reverseList(head.next);
listNode.next.next = listNode.next;
listNode.next = null;
return listNode;
}