解析未补充
理论基础
链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null
删除节点
删除D结点，只需要将C结点的下一个结点指向E结点即可
添加节点
只需要将C结点的下一个结点指向新结点，新结点下一个结点指向D结点
注意：链表的增添和删除都是O(1)操作，也不会影响到其他节点
但是如果要删除第五个节点，需要从头节点查找到第四个节点通过next指针进行删除操作，查找的时间复杂度是O(n)
题目
双指针
1
2
3
4
5
6
7
8
9
10
11
| public ListNode reverseList(ListNode head) {
ListNode temp = head;
ListNode pre = null;
while (temp != null) {
ListNode next = temp.next;
temp.next = pre;
pre = temp;
temp = next;
}
return pre;
}
|
递归
从后向前递归
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
| class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
class MyLinkedList {
int size;
ListNode head;
public MyLinkedList() {
size = 0;
head = new ListNode(0);
}
public int get(int index) {
if (index < 0 || index >= size) {
return -1;
}
ListNode temp = head;
for (int i = 0; i < index + 1; i++) {
temp = temp.next;
}
return temp.val;
}
public void addAtHead(int val) {
addAtIndex(0,val);
}
public void addAtTail(int val) {
addAtIndex(size,val);
}
public void addAtIndex(int index, int val) {
if (index > size){
return;
}
++size;
ListNode pre = head;
ListNode newNode = new ListNode(val);
for (int i = 0; i < index; i++) {
pre = pre.next;
}
newNode.next = pre.next;
pre.next = newNode;
}
public void deleteAtIndex(int index) {
if (index < 0 || index >= size) {
return;
}
--size;
ListNode pre = head;
for (int i = 0; i < index; i++) {
pre = pre.next;
}
pre.next = pre.next.next;
}
}
|
递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode next = head.next;
ListNode newNode = swapPairs(next.next);
next.next = head;
head.next = newNode;
return next;
}
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
15
16
17
18
19
20
21
22
23
| public ListNode swapPairs(ListNode head) {
ListNode dummyNode = new ListNode(0);
dummyNode.next = head;
ListNode temp = dummyNode;
while (temp.next != null && temp.next.next != null) {
ListNode third = head.next.next;
temp.next = head.next;
head.next.next = head;
head.next = third;
temp = head;
head = head.next;
}
return dummyNode.next;
}
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
15
16
17
18
19
20
21
22
| public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummyNode = new ListNode(0);
dummyNode.next = head;
ListNode fast = dummyNode;
ListNode slow = dummyNode;
for (int i = 0; i < n; i++) {
fast = fast.next;
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummyNode.next;
}
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
15
16
17
18
19
20
21
22
| public ListNode removeNthFromEnd(ListNode head, int n) {
int length = 0;
ListNode dummy = new ListNode(0,head);
ListNode temp = dummy;
while (temp.next != null) {
temp = temp.next;
length++;
}
temp = dummy;
for (int i = 1; i < length - n + 1; ++i) {
temp = temp.next;
}
temp.next = temp.next.next;
return dummy.next;
}
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
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
| public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int lengthA = 0;
int lengthB = 0;
ListNode dummyA = headA;
ListNode dummyB = headB;
while (dummyA != null){
lengthA++;
dummyA = dummyA.next;
}
while (dummyB != null){
lengthB++;
dummyB = dummyB.next;
}
dummyA = headA;
dummyB = headB;
if (lengthB > lengthA) {
int tmpLen = lengthA;
lengthA = lengthB;
lengthB = tmpLen;
ListNode tmpNode = dummyA;
dummyA = dummyB;
dummyB = tmpNode;
}
int gap = lengthA - lengthB;
while (gap-- > 0) {
dummyA = dummyA.next;
}
while (dummyA != null) {
if (dummyA == dummyB) {
return dummyA;
}
dummyA = dummyA.next;
dummyB = dummyB.next;
}
return null;
}
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
|
