链表常见问题
1
2
3
4
5
6
7
8
9
10
|
class Node {
int val;
Node next;
public Node(int val) {
this.val = val;
}
}
|
0x01 链表翻转
题目描述：
这道算法题，说直白点就是：如何让后一个节点指向前一个节点。
1
2
3
4
5
6
7
8
9
10
11
|
public static Node reverse(Node head) {
Node res = null;
while (head != null) {
Node h = head.next;
head.next = res;
res = head;
head = h;
}
return res;
}
|
0x02 两数相加
题目描述：
Leetcode:给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例：
1
2
3
| 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public static Node plus(Node l1, Node l2) {
Node dummyHead = new Node(0);
Node l3 = dummyHead;
int carry = 0;
while (l1 != null || l2 != null || carry > 0) {
int val = carry;
val = (l1 != null ? val + l1.val : val);
val = (l2 != null ? val + l2.val : val);
Node t = new Node(val > 9 ? val - 10 : val);
l3.next = t;
carry = val > 9 ? 1 : 0;
l1 = l1 != null ? l1.next : null;
l2 = l2 != null ? l2.next : null;
l3 = t;
}
return dummyHead.next;
}
|
0x03 链表中倒数第k个节点
题目描述：
输入一个链表，输出该链表中倒数第k个结点。
问题分析：
链表中倒数第k个节点也就是正数第(L-K+1)个节点。
首先两个节点/指针，一个节点 node1 先开始跑，指针 node1 跑到 k-1 个节点后，另一个节点 node2 开始跑，当 node1 跑到最后时，node2 所指的节点就是倒数第k个节点也就是正数第(L-K+1)个节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public static Node findKFromEnd(Node head, int k) {
Node node1 = head, node2 = head;
int len = 0, index = k;
while (node1 != null) {
len++;
node1 = node1.next;
if (index > 0) {
index--;
} else {
node2 = node2.next;
}
}
if (len == 0 || len < k) return null;
return node2;
}
|
0x04 删除链表的倒数第N个节点
题目描述：
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
问题分析:
首先我们将添加一个 哑结点(dummyHead)作为辅助，该结点位于列表头部。哑结点用来简化某些极端情况，例如列表中只含有一个结点，或需要删除列表的头部。在第一次遍历中，我们找出列表的长度 L。然后设置一个指向哑结点的指针，并移动它遍历列表，直至它到达第 (L - n) 个结点那里。我们把第 (L - n)个结点的 next 指针重新链接至第 (L - n + 2)个结点，完成这个算法。
链表中倒数第N个节点也就是正数第(L-N+1)个节点。 定义两个节点 node1、node2;node1 节点先跑，node1节点 跑到第 n+1 个节点的时候,node2 节点开始跑.当node1 节点跑到最后一个节点时，node2 节点所在的位置就是第 （L-n ） 个节点（L代表总链表长度，也就是倒数第 n+1 个节点）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public static Node deleteKFromEnd(Node head, int k) {
Node dummyHead = new Node(0);
dummyHead.next = head;
int len = 0, index = k;
Node p1 = head, p2 = dummyHead;
while (p1 != null) {
len++;
p1 = p1.next;
if (index > 0) {
index--;
} else {
p2 = p2.next;
}
}
if (len >= k && k > 0) {
p2.next = p2.next.next;
}
return dummyHead.next;
}
|
0x05 合并两个有序的链表
题目描述：
输入两个单调递增的链表，输出两个链表合成后的链表，需要合成后的链表单调递增。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public static Node merge(Node head1, Node head2) {
if (head1 == null) return head2;
if (head2 == null) return head1;
Node t = null;
if (head1.val < head2.val) {
t = head1;
t.next = merge(head1.next, head2);
} else {
t = head2;
t.next = merge(head1, head2.next);
}
return t;
}
|