找出两个链表的交点
链接
设A的长度为a+c，B的长度为b+c，其中c为公共部分长度。
可以推出以下公式：
a+c+b=b+c+a
当访问 A 链表的指针访问到链表尾部时，令它从链表 B 的头部开始访问链表 B；同样地，当访问 B 链表的指针访问到链表尾部时，令它从链表 A 的头部开始访问链表 A。
- 若存在交点，直接通过if语句可以判断出来
- 若不存在交点，则两个链表尾节点同时为null，也可退出循环
1
2
3
4
5
6
7
8
9
10
11
| public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode a = headA;
ListNode b = headB;
while (a != b) {
a = (a == null) ? headB : a.next;
b = (b == null) ? headA : b.next;
}
return a;
}
}
|
链表反转
链接
直接背下这段递归代码吧
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode next = head.next;
ListNode newHead = reverseList(next);
next.next = head;
head.next = null;
return newHead;
}
}
|
归并两个有序链表
链接
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
| class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if (list1 == null) {
return list2;
} else if (list2 == null) {
return list1;
}
ListNode newHead = new ListNode();
if (list1.val <= list2.val) {
newHead = list1;
list1 = list1.next;
} else {
newHead = list2;
list2 = list2.next;
}
ListNode now = newHead;
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
now.next = list1;
list1 = list1.next;
now = now.next;
} else {
now.next = list2;
list2 = list2.next;
now = now.next;
}
}
if (list1 != null) {
now.next = list1;
} else if (list2 != null) {
now.next = list2;
}
return newHead;
}
}
|
从有序链表中删除重复节点
链接
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode originalHead = head;
while (head != null) {
ListNode next = head.next;
while (next != null && next.val == head.val) {
next = next.next;
}
head.next = next;
head = head.next;
}
return originalHead;
}
}
|
删除链表的倒数第n个节点
链接
删除倒数第n个节点，就是改变倒数第n+1个节点的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
| class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
int m = 0;
ListNode originalHead = head;
while (head != null) {
m++;
head = head.next;
}
m = m - n;
if (m == 0) {
return originalHead.next;
}
int now = 0;
head = originalHead;
while (head != null) {
now++;
if (now == m) {
head.next = head.next.next;
}
head = head.next;
}
return originalHead;
}
}
|
交换链表中的相邻节点
链接
大概要改变三个东西：
- 将上组的next改为该组的偶数下标元素
- 偶数下标元素的next指向前一个元素
- 奇数下标元素的next指向下一个奇数下标元素
然后继续迭代下去，直到任意元素为null
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 swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode pre = new ListNode();
ListNode originalHead = head.next;
pre.next = head;
ListNode a = head;
ListNode b = head.next;
while (a != null && b != null) {
pre.next = b;
pre = a;
a.next = b.next;
b.next = a;
a = a.next;
if (a != null)
b = a.next;
}
return originalHead;
}
}
|
链表求和
链接
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
注意下最后构造链表的时候要反着来，因为相加时已经利用了栈。
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 {
private Stack<Integer> build(ListNode head) {
Stack<Integer> stk = new Stack<>();
while (head != null) {
stk.push(head.val);
head = head.next;
}
return stk;
}
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> a = build(l1);
Stack<Integer> b = build(l2);
int ten = 0;
ListNode head = null;
while (!a.isEmpty() || !b.isEmpty() || ten != 0) {
int x = (a.isEmpty()) ? 0 : a.pop();
int y = (b.isEmpty()) ? 0 : b.pop();
int sum = x + y + ten;
ten = sum / 10;
ListNode preHead = new ListNode(sum % 10);
preHead.next = head;
head = preHead;
}
return head;
}
}
|
回文链表
链接
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public boolean isPalindrome(ListNode head) {
Stack<Integer> stk = new Stack<>();
ListNode originalHead = head;
while (head != null) {
stk.push(head.val);
head = head.next;
}
head = originalHead;
while (!stk.isEmpty()) {
if (stk.pop() != head.val) {
return false;
}
head = head.next;
}
return true;
}
}
|
分割链表
链接
把链表分割成k部分，每部分的长度最多相差1.这 k 个部分应该按照在链表中出现的顺序排列，并且排在前面的部分的长度应该大于或等于排在后面的长度。
这里考察了删除节点（大概），但是删除的东西是判断是否继续循环的条件。所以要定义一个临时变量记录这个被删除的节点。
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
| class Solution {
public ListNode[] splitListToParts(ListNode head, int k) {
int n = 0;
ListNode originalHead = head;
while (head != null) {
n++;
head = head.next;
}
int left = n % k;
int count = n / k;
ListNode[] ans = new ListNode[k];
head = originalHead;
for (int i = 0; i < k; i++) {
int m = count;
if (i < left) {
m = count + 1;
}
ans[i] = head;
for (int j = 0; j < m - 1; j++) {
head = head.next;
}
if (head != null) {
ListNode tmp = head.next;
head.next = null;
head = tmp;
}
}
return ans;
}
}
|
奇偶链表
链接
将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
记录以下信息：奇数链表尾节点，偶数链表头节点。
各自记录奇数链表盒偶数链表，跑完后让奇数链表的尾节点指向偶数链表头节点即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null) {
return head;
}
ListNode odd = head;
ListNode even = head.next;
ListNode evenHead = even;
while (even != null && even.next != null) {
odd.next = odd.next.next;
even.next = even.next.next;
odd = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
}
|
版权声明: 此文章版权归金晖のBlog所有，如有转载，请注明来自原作者
