目录
  1. 1、两个单链表求和
  2. 2、单链表非递归翻转,不借助其他数据结构
  3. 3、回文链表(用 O(n) 时间复杂度和 O(1) 空间复杂度)
  4. 4、环形链表
  5. 5、删除链表种所有值为val的节点
  6. 6、合并两个有序链表
  7. 总结
链表的常见算法总结

1、两个单链表求和

445. 两数相加 II
双栈法更好理解。

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
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//双栈法
LinkedList<ListNode> stack1 = new LinkedList<>();
LinkedList<ListNode> stack2 = new LinkedList<>();
ListNode res = null;
while (l1 != null) {
stack1.push(l1);
l1 = l1.next;
}
while (l2 != null) {
stack2.push(l2);
l2 = l2.next;
}
//进位
int carry = 0;
while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
int sum = 0;
if (!stack1.isEmpty()) {
sum += stack1.pop().val;
}
if (!stack2.isEmpty()) {
sum += stack2.pop().val;
}
sum += carry;
//进位
carry = sum / 10;
//和取模
ListNode node = new ListNode(sum % 10);
node.next = res;
res = node;
}
return res;
}

将两个链表构造两个栈,使用栈先进后出的特性,做两个链表倒叙做计算,注意进位的情况。

2、单链表非递归翻转,不借助其他数据结构

206. 反转链表
单链表的翻转就是将相邻两个节点的指针翻转。需要借助两个额外的指针用来存储当前节点的前后节点。

1
2
3
4
5
6
7
8
9
10
public static ListNode reverseList(ListNode head) {
ListNode pre = null;
while(head!=null){
ListNode temp = head.next;
head.next = pre;
pre = head;
head = temp;
}
return pre;
}

3、回文链表(用 O(n) 时间复杂度和 O(1) 空间复杂度)

234. 回文链表
通过快慢指针获取链表中间节点位置,将后半段链表反转,之后迭代前后链表,判断值是否相同。

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
public static boolean isPalindrome(ListNode head) {
//边界检查,如果链表为空,或者只有一个节点,直接返回true
if (head == null || head.next == null) {
return true;
}
//使用快慢指针获取链表中间节点位置
ListNode fast = head;
ListNode slow = head;
//当有偶数个节点时,fast为null时,到达终点
//当有奇数个节点时,fast.next为null,到达终点
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//到达终点时,奇数个节点,slow正好处于中间位置,偶数个节点时slow处于后半段的开始位置。
//slow作为前半段链表起点,fast作为后半段链表起点
fast = slow;
slow = head;
//反转fast开头的后半段链表
ListNode pre = null;
while (fast != null) {
ListNode temp = fast.next;
fast.next = pre;
pre = fast;
fast = temp;
}
//迭代slow与pre,比较每个值
while (slow != null && pre != null) {
if(slow.val!=pre.val){
return false;
}
slow = slow.next;
pre = pre.next;
}
return true;
}

4、环形链表

141. 环形链表
检测链表中是否有环,可以使用两种方法:使用HashSet或者快慢指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static boolean hasCycle(ListNode head) {
//边界检查,如果链表为空或者只有一个节点,直接返回false
if (head == null || head.next == null) {
return false;
}
//使用快慢指针
ListNode fast = head.next;
ListNode slow = head;
//快慢指针没有重合就一直循环
while (fast != slow) {
//只要快指针到达链表尾部,则无环
if (fast == null || fast.next == null) {
return false;
}
fast = fast.next.next;
slow = slow.next;
}
return true;
}

5、删除链表种所有值为val的节点

203. 移除链表元素
链表移除操作要借助一个哨兵节点,简化删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static ListNode removeElements(ListNode head, int val) {
//使用哨兵节点
ListNode sentinel = new ListNode(0);
sentinel.next = head;
ListNode pre = sentinel;
while (head != null) {
//如果当前的节点就是要删除的节点
if (head.val == val) {
//前一个节点直接指向后一个节点
pre.next = head.next;
} else {
//pre向后移动
pre = head;
}
head = head.next;
}
return sentinel.next;
}

6、合并两个有序链表

21. 合并两个有序链表
需要使用哨兵节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//定义哨兵节点
ListNode head = new ListNode(0);
ListNode pre = head;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
pre.next = l1;
l1 = l1.next;
} else {
pre.next = l2;
l2 = l2.next;
}
pre = pre.next;
}
if (l1 == null) {
pre.next = l2;
} else {
pre.next = l1;
}
return head.next;
}

总结

链表常用的算法经常会借助快慢指针和哨兵节点。只要用到哨兵节点head就会有pre节点相配合。

tencent.jpg

文章作者: ClawHub
文章链接: https://www.clawhub.club/posts/2020/01/06/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E9%93%BE%E8%A1%A8%E7%9A%84%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 ClawHub的博客
打赏
  • 微信
  • 支付宝
扫一扫关注ClawHub公众号,专注Java、技术分享、面试资源。