Java实现链表
class Solution {
public static void main(String[] args) {
ListNode node = new ListNode(
1,
new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5))))
);
System.out.println("原链表:" + node);
// System.out.println("反转后的链表:" + reverseList(node));
// System.out.println("0-2反转结果:" + reverseList(node,2));
// System.out.println("2-4反转结果:" + reverseList(node,2,4));
}
// 从left节点开始到right节点反转
public static ListNode reverseList(ListNode head, int left, int right) {
if (null == head || null == head.next) {
return head;
}
int num = right - left + 1;
if (num < 1) {
return head;
}
// 定义一个虚头
ListNode xHead = new ListNode(0, head);
ListNode leftNode = xHead;
for (int i = left; i > 1; i--) {
leftNode = leftNode.next;
}
leftNode.next = reverseList(leftNode.next, num);
return xHead.next;
}
// 从开始反转num个节点
public static ListNode reverseList(ListNode head, int num) {
if (num == 1 || null == head || null == head.next) {
return head;
}
ListNode tail = head.next;
ListNode cur = reverseList(head.next, num - 1);
head.next = tail.next;
tail.next = head;
return cur;
}
// 链表反转
public static ListNode reverseList(ListNode head) {
if (null == head || null == head.next) {
return head;
}
// 后面节点反转后的尾节点
ListNode tail = head.next;
ListNode cur = reverseList(head.next);
head.next = tail.next;
tail.next = head;
return cur;
}
public static class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
@Override
public String toString() {
ListNode node = this;
StringBuffer buffer = new StringBuffer();
while(null != node){
buffer.append(node.val);
buffer.append(">");
node = node.next;
}
return buffer.substring(0,buffer.length()-1).toString();
}
}
}
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
编辑此页 (opens new window)
上次更新: 2021/03/07 14:59:48