24 两两交换链表中的节点
https://leetcode.com/problems/swap-nodes-in-pairs/description/
正常模拟交换过程
首先建立dummy节点，之后设置第一节点，第二节点，temp
while 判断是否有两个节点可以交换
模拟过程：
存储cur的第三个节点
存储cur的第二个节点
存储cur的第一个节点
cur的next是第二个节点
第二个节点的next是第一个节点
第一个节点的next是第三个节点
之后cur移到第一个节点的位置（即新虚拟节点的位置）
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
| class Solution{
public ListNode swapPairs(ListNode head){
ListNode temp;
ListNode firstNode;
ListNode secondNode;
ListNode dummy = new ListNode(-1, head);
ListNode cur = dummy;
while (cur.next != null && cur.next.next != null){
temp = cur.next.next.next;
firstNode = cur.next;
secondNode = cur.next.next;
cur.next = secondNode;
secondNode.next = firstNode;
firstNode.next = temp;
cur = firstNode;
}
return dummy.next;
}
}
|
递归方法： 类似翻转链表中反向递归方法（需要研究）不是很明白
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution{
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;
}
}
|
19 删除链表倒数第N个节点
https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/
自己可以写出两次遍历的解法：
第一次找到size
第二次把节点删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution{
public ListNode removeNthFromEnd(ListNode head, int n){
ListNode dummy = new ListNode(-1,head);
ListNode pre = dummy;
ListNode cur = head;
int size = 0;
while (cur != null){
cur = cur.next;
size++;
}
for (int i = 0; i < size - n; i++){
pre = pre.next;
}
pre.next = pre.next.next;
return dummy.next;
}
}
|
快慢指针经典题目
设置双指针，快指针先走n步，后快指针和慢指针一起走到快指针的链表尽头，此时删除慢指针所指node
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution{
public ListNode removeNthFromEnd(ListNode head, int n){
ListNode dummy = new ListNode(-1, head);
ListNode fastNode = dummy;
ListNode slowNode = dummy;
for (int i = 0; i <= n; i++){
fastNode = fastNode.next;
}
while (fastNode != null){
fastNode = fastNode.next;
slowNode = slowNode.next;
}
slowNode.next = slowNode.next.next;
return dummy.next;
}
}
|
160 链表相交
https://leetcode.com/problems/intersection-of-two-linked-lists/description/
求两链表交点节点的指针
首先求出两链表的长度
把两个链表的尾部对齐，即把长链表的指针指到和短链表相同长度
如果指针数值相同则相交，否则向后移动指到null
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
| public class Solution{
public ListNode getIntersectionNode(ListNode headA, ListNode headB){
ListNode curA = headA;
ListNode curB = headB;
int sizeA = 0;
int sizeB = 0;
while (curA != null){
curA = curA.next;
sizeA++;
}
while (curB != null){
curB = curB.next;
sizeB++;
}
curA = headA;
curB = headB;
if (sizeA < sizeB){
for (int i = 0; i < sizeB-sizeA; i++){
curB = curB.next;
}
} else if (sizeA > sizeB){
for (int i = 0; i < sizeA-sizeB; i++){
curA = curA.next;
}
}
while (curA != null){
if(curA == curB){
return curA;
} else {
curA = curA.next;
curB = curB.next;
}
}
return null;
}
}
|
142 环形链表II
https://leetcode.com/problems/linked-list-cycle-ii/description/
判断链表内是否有环：
可通过快慢指针来判断，快走两步，慢走一步，这样如果两指针相遇，则链表内定存在环
如果有环如何判断环入口：
通过公式化简可得：
如果快指针走过一圈后就遇到慢指针，则从遇到的点开始和头节点同时走相同步数，两指针相遇的点即为入口
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
| class Solution{
public ListNode detectCycle(ListNode head){
ListNode slowIndex = head;
ListNode fastIndex = head;
while (fastIndex != null && fastIndex.next != null){
slowIndex = slowIndex.next;
fastIndex = fastIndex.next.next;
if (slowIndex == fastIndex){
ListNode index1 = slowIndex;
ListNode index2 = head;
while (index1 != index2){
index1 = index1.next;
index2 = index2.next;
}
return index1;
}
}
return null;
}
}
|