【Java 优选算法】链表

欢迎关注个人主页：逸狼

创造不易，可以点点赞吗~

如有错误，欢迎指出~

尽量多new节点

2. 两数相加

解法

模拟两数相加即可,利用尾插法, 用 t 代表进位

cur.next = new ListNode(t % 10);

cur = cur.next

t /= 10

代码

/*** 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 addTwoNumbers(ListNode l1, ListNode l2) {ListNode head = new ListNode(0);ListNode prev = head;int t = 0;while(l1 != null || l2 != null || t != 0 ){//加上第一个链表if(l1 != null){t += l1.val;l1 = l1.next;}//加上第二个链表if(l2 != null){t += l2.val;l2 = l2.next;}prev.next = new ListNode(t % 10);prev = prev.next;t /= 10;}return head.next;}
}

24. 两两交换链表中的节点

完成这题只能通过修改指针,不能直接修改值

解法

循环, 迭代(模拟),根据画图模拟过程

处理特殊情况,head==null或者head.next==null时(空链表或者只有一个节点), 直接返回, 除此之外表示链表至少有两个节点cur和next

定义头节点newhead= prev ,建立连接prev.next = head,

定义cur = head, next = cur.next, nnext = next;

代码

/*** 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 swapPairs(ListNode head) {if(head == null || head.next == null) return head;ListNode newhead = new ListNode(0);newhead.next = head;ListNode prev = newhead;ListNode cur = head;ListNode next = cur.next;ListNode nnext = next.next;while(cur != null && next != null){//交换节点prev.next = next;next.next = cur;cur.next = nnext;//修改指针prev = cur;//注意顺序cur = nnext;if(cur != null) next = cur.next;//对于偶数情况if(next != null) nnext= next.next;//对于奇数}return newhead.next;}
}

143. 重排链表

解法

找到链表的中间节点: 快慢双指针
把后面的部分逆序: 头插法
合并两个链表

这里两种方法都可以使用,但是推荐使用方法1 (方法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 void reorderList(ListNode head) {//空链表 || 一个节点 || 两个节点 直接返回if(head == null || head.next == null || head.next.next == null) return;//找到中间节点ListNode slow = head, fast = head;while(fast != null && fast.next != null){slow = slow.next;fast = fast.next.next;}ListNode head2 = new ListNode(0);ListNode cur = slow.next;slow.next = null;//把两个链表分离//后半部分逆序(将slow后面的节点都逆序)while(cur != null){ListNode next = cur.next;cur.next = head2.next;head2.next = cur;cur = next;}//合并两个链表ListNode cur1 = head;ListNode cur2 = head2.next;while(cur1 != null && cur2 != null){//链表1更长//合并链表ListNode next1 = cur1.next;ListNode next2 = cur2.next;cur1.next = cur2;cur2.next = next1;cur1 = next1;cur2 = next2;      }}
}

23. 合并 K 个升序链表

解法

解法1: 暴力解法,每次将第二个链表合并到第一个上面,O(n* k^2)

解法二: 利用优先级队列做优化O(n* k* logk): 创建一个小根堆,将每个链表(题目给的链表都是升序的)的第一个节点放到小根堆里,取出堆顶元素对应的链表,cur节点右移

解法三: 分治-递归O(n* k* logk)

代码

解法二

/*** 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) {//创建一个小根堆PriorityQueue<ListNode> heap = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);//2.把所有头节点放到小根堆里for(ListNode head : lists){if(head != null){heap.offer(head);}}//3.合并链表ListNode ret = new ListNode(0);ListNode prev = ret;while(!heap.isEmpty()){ListNode t = heap.poll();prev.next = t;prev = t;if(t.next != null) heap.offer(t.next);}return ret.next;}
}

解法二

/*** 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) {return merge(lists, 0, lists.length - 1);}public ListNode merge(ListNode[] lists, int left, int right) {if (left > right) {return null;}if (left == right) {return lists[left];}int mid = (left + right) / 2;ListNode l1 = merge(lists, left, mid);ListNode l2 = merge(lists, mid + 1, right);return mergeTwoList(l1, l2);}public ListNode mergeTwoList(ListNode l1, ListNode l2) {if (l1 == null) {return l2;}if (l2 == null) {return l1;}if (l1.val < l2.val) {l1.next = mergeTwoList(l1.next, l2);return l1;} else {l2.next = mergeTwoList(l1, l2.next);return l2;}}
//代码超时了
public ListNode mergeTwoList(ListNode l1, ListNode l2){if(l1 == null) return l2;if(l2 == null) return l1;//合并两个有序链表ListNode head = new ListNode(0);ListNode cur1 = l1, cur2 = l2, prev = head;while(cur1 != null && cur2 != null){if(cur1.val < cur2.val){prev.next = cur1;prev = cur1;cur1 = cur1.next;}else {prev.next = cur2;prev = cur2;cur2 = cur2.next;}}while(cur1 != null) prev.next = cur1;while(cur2 != null) prev.next = cur2;return head.next;}
}

在分治法的基础上，可以进一步优化合并过程，减少不必要的遍历。例如，在 mergeTwoList 方法中，可以使用递归的方式来合并两个链表，这样可以使代码更加简洁，并且避免一些重复的操作。

25. K 个一组翻转链表

解法

每次用tmp标记要头插的第一个节点,头插k个节点后让prev = tmp,即下一次要头插的位置

代码

/*** 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 reverseKGroup(ListNode head, int k) {if(head == null) return head;//先求出需要逆序多少组ListNode cur = head;int n = 0;while(cur != null){n++;cur = cur.next;}n /= k;//重复n次: 长度为k的链表的逆序ListNode newHead = new ListNode(0);ListNode prev = newHead;cur = head;for(int i = 0; i < n; i++){//每次逆序之前记录第一个节点tmpListNode tmp = cur;for(int j = 0; j < k; j++){//头插逻辑ListNode next = cur.next;cur.next = prev.next;prev.next = cur;cur = next;}//头插完一轮后,更新prevprev = tmp;}//把后面不需要逆序部分连接上prev.next= cur;return newHead.next;}
}