【数据结构】【链表专题】链表常用的编程技巧
【摘要】 必备知识链表是一种兼具递归和迭代性质的数据结构，常用技巧：双指针中的快慢指针。一、合并两个有序链表（虚拟头结点）/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(in...
必备知识
链表是一种兼具递归和迭代性质的数据结构，常用技巧：双指针中的快慢指针。
一、合并两个有序链表（虚拟头结点）
/**
* Definition for singly-linked list.
* 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; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNod
e list1, ListNode list2) {
ListNode result = new ListNode();// 使用虚拟头结点：第一个节点为空，从第二个节点开始才是想要的
ListNode p = result;
ListNode p1 = list1,p2 = list2;
while(p1 != null && p2!=null) {
if(p1.val > p2.val) {
p.next = p2;
p2 = p2.next;
} else {
p.next = p1;
p1 = p1.next;
}
p = p.next;
}
while(p1 != null) {
p.next = p1;
p1 = p1.next;
p = p.next;
}
while (p2 != null) {
p.next = p2;
p2= p2.next;
p = p.next;
}
return result.next;
}
}
思路：
合并两个单链表：
1.使用双指针循环遍历，两个单链表同时遍历比较；然后移动指针
2.两个单链表同时遍历完后，最多会剩下一个单链表还有值，需要将剩下的也合并。
3.两个单链表都需要判断一下是否为空，不空就合并，最后返回合并后的链表
4.可以使用虚拟头结点进行辅助
二、合并K个有序链表（虚拟头结点和二叉堆）
/**
* Definition for singly-linked list.
* 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; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
ListNode result = new ListNode();
ListNode temp = result;
if(lists.length == 0) {
return null;
}
PriorityQueue<ListNode> minHead = new PriorityQueue<>(lists.length, Comparator.comparingInt(o -> o.val));
for (ListNode node: lists
) {
if (node != null){
minHead.offer(node);
}
}
while (!minHead.isEmpty()) {
ListNode node = minHead.poll();
temp.next = node;
if (node.next != null) {
minHead.offer(node.next);
}
temp = temp.next;
}
return result.next;
}
}思路：
- 分析题目，合并K个有序的链表，则需要找出这K个链表中最小的那个节点，使用优先队列-二叉堆-最小堆得特性，辅助
- 创建一个虚机头结点的结果链表
- 遍历将K个链表先放进优先队列中，因为是有序的，则第一批放进去的肯定存在最小的节点
- 再一个个出队列，第一个出队的就是最小，将最小的节点放到结果链表中，然后再将最小节点的下一个节点放进优先队列中进行排序
- 最后将一个个出队，放到结果链表，返回即可。
三、删除链表中倒数第N个结点（同步双指针）
/**
* Definition for singly-linked list.
* 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; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode result = new ListNode(-1);
ListNode dump = result;
ListNode p1 = head;
for(int i =0; i< n; i++) {
p1 = p1.next;
}
ListNode p2 = head;
while(p1 != null) {
result.next = p2;
p2 = p2.next;
result = result.next;
p1 = p1.next;
}
result.next = p2.next;
return dump.next;
}
}
寻找第k个节点思路：使用双指针
// 返回链表的倒数第 k 个节点
ListNode findFromEnd(ListNode head, int k) {
ListNode p1 = head;
// p1 先走 k 步
for (int i = 0; i < k; i++) {
p1 = p1.next;
}
ListNode p2 = head;
// p1 和 p2 同时走 n - k 步
while (p1 != null) {
p2 = p2.next;
p1 = p1.next;
}
// p2 现在指向第 n - k 个节点
return p2;
}四、返回链表中的中间结点（快慢双指针）
/**
* Definition for singly-linked list.
* 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; }
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
ListNode show = head;
ListNode fast = head;
while(show !=null && fast !=null && fast.next !=null) {
show = show.next;
fast = fast.next.next;
}
return show;
}
}思路：
如果知道链表的长度N，即可返回其中间结点了，问题在于长度N未知，如何一次遍历寻找其长度。
使用快慢指针，快指针每次走两步，慢指针每次走一步，快慢刚好相差两倍，当快指针走到最后时，慢指针刚好走到中间
五、有环的链表
1.判断链表是否有环（使用快慢双指针）
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode show = head;
while (show != null && fast != null && fast.next != null) {
fast = fast.next.next;
show = show.next;
if (fast == show) {
return true;
}
}
return false;
}
}思路：
使用快慢双指针，如果有环，则快慢指针一定相遇（即相等）则是有环，如果最后是null则没有环
2.返回有环链表的起点（先使用快慢双指针找到环，再使用同步双指针找到相遇点）
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode show = head;
while(show != null && fast !=null && fast.next != null) {
show = show.next;
fast = fast.next.next;
if (show == fast) {
break;
}
}
if(fast == null || fast.next == null) {
return null;
}
show = head;
while(show != fast) {
show = show.next;
fast = fast.next;
}
return show;
}
}思路：
1.先使用快指针找到是否有环，并知道所在环的路径
2.然后快指针在成环的位置上，慢指针在起点，同时移动指针，如果再次相遇即是，入环的第一个起点了
六、相交链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode one = headA;
ListNode two = headB;
while (one != two) {
if (one == null) {
one = headB;
} else {
one = one.next;
}
if(two == null) {
two = headA;
} else {
two = two.next;
}
}
return one;
}
}思路：
两条链表同时遍历，A遍历完就接着遍历B，B遍历完就接着遍历A，由于最后遍历的次数是相同，如果遇到相同节点，就是相交的节点，如果没有相交，则最后都是null.
七、反转链表
1.反转全链表
/**
* Definition for singly-linked list.
* 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; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null) {
return head;
}
ListNode last = reverseList(head.next);
head.next.next = head;
head.next = null;
return last;
}
}思路：
利用递归，后序遍历，将相邻的两个节点的指针给换位置即可。
2.反转前N个结点
Class Solusion {
ListNode rear = null;
Public ListNode reverseListN(ListNode head, int n) {
If (n == 1) {
rear = head.next;
}
ListNode last = reverseListN(head.next, n-1);
head.next.next = head;
head.next = rear;
}
return last;
}- 反转区间结点的链表
/**
* Definition for singly-linked list.
* 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; }
* }
*/
class Solution {
ListNode rear = null;
public ListNode reverseBetween(ListNode head, int left, int right) {
if (left == 1) {
return reverseListN(head, right);
}
head.next = reverseBetween(head.next,left-1,right-1);
return head;
}
ListNode reverseListN(ListNode head, int n) {
if (n == 1) {
rear = head.next;
return head;
}
ListNode last = reverseListN(head.next, n-1);
head.next.next = head;
head.next = rear;
return last;
}
}思路：
1.现将区间和链表同时移动，直到是从1开始反转，也就是只反转前几个节点就可以了
2.调用反转前N个结点的递归方法即可
- k个一组反转链表
思路：使用迭代性质，前序遍历
- 先反转head开头的第k个结点
- 接着反转第k+1个元素为head递归调用reverseKGroup函数
- 最后将反转的结果接上即可。
八、判断回文单链表；
方法1：将原链表反转成一条新链表保存起来，然后两条链表同时比较即可判断是否是回文链表
/**
* Definition for singly-linked list.
* 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; }
* }
*/
class Solution {
ListNode newHead = new ListNode(-1);
public boolean isPalindrome(ListNode head) {
ListNode p2 = newHead;
ListNode p3 = reverse(head);
p2 = p2.next;
while(p2 != null) {
if(p2.val != p3.val) {
return false;
}
p2 = p2.next;
p3 = p3.next;
}
return true;
}
ListNode reverse(ListNode head) {
newHead.next = new ListNode(head.val);
newHead = newHead.next;
if (head == null || head.next == null) {
return head;
}
ListNode last = reverse(head.next);
head.next.next = head;
head.next = null;
return last;
}
}方法2：使用二叉树的后序遍历
/**
* Definition for singly-linked list.
* 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; }
* }
*/
class Solution {
ListNode left = null;
boolean flag = true;
public boolean isPalindrome(ListNode head) {
left = head;
df(head);
return flag;
}
void df(ListNode right) {
if(right == null) {
return;
}
df(right.next);
if(left.val != right.val) {
flag = false;
}
left = left.next;
}
}
方法3：先找到中点，取中点前面部分保存，然后翻转后面部分，保存，最后两部分进行比较即可（利用类似二分法的方式）
九、使用快慢指针-删除链表中重复元素
/**
* Definition for singly-linked list.
* 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; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null) {
return head;
}
ListNode show = head;
ListNode fast = head.next;
while(fast != null) {
if(show.val == fast.val) {
fast = fast.next;
continue;
}
show.next = fast;
fast = fast.next;
show = show.next;
}
show.next = null;
return head;
}
}思路：
1.使用快慢双指针
2.慢指针与快指针相比较，快指针在前面探路，如果快慢指针的值不相等，则将慢指针的位置值替换成快指针的，然后双方继续前进一步
3.最后将慢指针的next置为null并返回头链表
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）