【算法】【优选算法】链表
目录
一、链表常用技巧与操作总结
技巧：
- 画图解题。
- 使用虚拟头结点。
- 像有插入类似操作时，直接定义变量，不用考虑节点丢失情况。
- 快慢指针。
操作：
- 创建新节点。
- 尾插。
- 头插。
二、2.两数相加
题目链接：2.两数相加
题目描述：
题目解析：
- 给你两个链表，每个链表都表示一个逆位的数，将两个数相加。
- 相加后的结果不会出现，链表最后节点为0的情况。
解题思路：
- 模拟两个数字相加即可。
- 遍历两个链表，对应节点值相加，放在一个变量sum中，结果链表就接上sum%10的节点，sum / 10表示进位的数。
解题代码：
//时间复杂度：O(n)//空间复杂度：O(1)classSolution{publicListNodeaddTwoNumbers(ListNode l1,ListNode l2){ListNode newHead =newListNode(0);//虚拟头结点ListNode pre = newHead;int sum =0;while(l1 !=null|| l2 !=null|| sum !=0){if(l1 !=null){ sum += l1.val; l1 = l1.next;}if(l2 !=null){ sum += l2.val; l2 = l2.next;} pre.next =newListNode(sum %10); pre = pre.next; sum /=10;}return newHead.next;}}三、24.两两交换链表中的节点
题目链接：24.两两交换链表中的节点
题目描述：
题目解析：
- 就交换两个相邻节点即可。
3.1 迭代
解题思路：
- 交换之后移动这四个变量即可，循环交换就可以了。
- 细节处理：当我们第一次定义变量的时候，为防止空指针异常，要将链表为空和链表为1个节点情况排除。
循环结束条件：当偶数节点个数的时候cur1为null时就该结束了。当奇数节点个数的时候cur2为null时结束。
直接就交换节点即可，为避免节点丢失情况，我们就将交换过程涉及到的节点定义出来即可，然后根据交换后节点直接一一连接即可。
解题代码：
//时间复杂度：O(n)//空间复杂度：O(1)classSolution{publicListNodeswapPairs(ListNode head){if(head ==null|| head.next ==null)return head;ListNode newHead =newListNode(0); newHead.next = head;ListNode pre = newHead;ListNode cur1 = pre.next;ListNode cur2 = cur1.next;ListNode last = cur2.next;while(cur1 !=null&& cur2 !=null){//交换 pre.next = cur2; cur2.next = cur1; cur1.next = last;//向后移动 pre = cur1;if(pre.next ==null)break; cur1 = pre.next;if(cur1.next ==null)break; cur2 = cur1.next; last = cur2.next;}return newHead.next;}}3.2 递归
解题思路
- 我们就交换两个节点，然后剩余节点又是一个待交换节点的链表。
- 结束条件：链表为空或链表为1个节点。
解题代码：
//时间复杂度：O(n)//空间复杂度：O(1)classSolution{publicListNodeswapPairs(ListNode head){if(head ==null|| head.next ==null)return head;ListNode newHead = head.next; head.next = newHead.next; newHead.next = head; head.next =swapPairs(head.next);return newHead;}}四、143.重排链表
题目链接：143.重排链表
题目描述：
题目分析：
- 就是将链表按照题目给的规则重新排序。
解题思路：
- 这道题其实就可以看成下面的3个步骤：
- 先找到中间节点，再将后半部分链表逆置，再将两个子链表分别取一个节点的连接在一起。
- 找到中间节点：使用快慢双指针。
- 方案一：将slow以及其后节点都逆置。
- 方案二：将slow后的节点逆置。因为本来slow和slow前一个节点在结果链表中的位置是不会变的。
- 因为方便处理两个链表不循环，要让两个子链表末尾都指向null，方案一还需要去记录slow前一个节点，所以采取方案二。
- 将两个子链表合并：直接连接即可。由于采取方案二，所以子链表1一定更长，使用这个当循环条件。
- 细节问题：当链表有1个和2个节点时，不需要交换，并且会导致空指针异常，单独处理。
后半部分链表逆置：逆置采用头插法逆置，但是从哪里开始逆置有说法：像下图由于节点数奇偶性不同，slow走到位置不同（可能是正中间节点，也可能是下一个节点）。我们有两个逆置方案
解题代码：
//时间复杂度：O(n)//空间复杂度：O(1)classSolution{publicvoidreorderList(ListNode head){if(head.next ==null|| head.next.next ==null)return;//快慢双指针 找到中间节点ListNode slow = head;ListNode fast = head;while(fast !=null&& fast.next !=null){ slow = slow.next; fast = fast.next.next;}//头插法 逆置ListNode head2 =newListNode(0);ListNode cur = slow.next; slow.next =null;while(cur !=null){ListNode next = cur.next; cur.next = head2.next; head2.next = cur; cur = next;} head2= head2.next;//合并两个链表ListNode newHead =newListNode(0);ListNode pre = newHead;while(head !=null){if(head !=null){ pre.next = head; head = head.next; pre = pre.next;}if(head2 !=null){ pre.next = head2; head2 = head2.next; pre = pre.next;}} head = newHead.next;}}五、23.合并K个升序链表
题目链接：23.合并K个升序链表
题目描述：
题目解析：
- 给一个链表数组，将元素合并为一个链表，按照升序排列。
5.1 堆
解题思路：
- 我们只需要使用一个小根堆来存储每次需要比较大小的节点，然后将最小的节点尾插放进结果链表。在将最小节点的后一个节点放入堆中即可。
- 入堆的时候，需要判断节点是不是为空，空节点不能进入堆。
- 当堆变空时，就完成合并了。
解题代码：
//时间复杂度：O(N*K*logK)//空间复杂度：O(k)classSolution{publicListNodemergeKLists(ListNode[] lists){PriorityQueue<ListNode> heap =newPriorityQueue<>((l1,l2)-> l1.val-l2.val);ListNode ret =newListNode(0);ListNode pre = ret;for(ListNode head : lists){if(head !=null) heap.offer(head);}while(!heap.isEmpty()){ListNode cur = heap.poll(); pre.next = cur; pre = pre.next; cur = cur.next;if(cur !=null) heap.offer(cur);}return ret.next;}}5.2 分治
解题思路：
- 与归并排序思路一模一样。
- 直接将数组拆分为两份，两份合并之后得到两个有序链表，再合并两个有序链表即可。
- 细节：链表数组可能为空，也可能是数组内元素为空，所以归并结束条件有所不同。
解题代码：
//时间复杂度：O(N*K*logK)//空间复杂度：O(k)classSolution{publicListNodemergeKLists(ListNode[] lists){returnmrege(0, lists.length-1,lists);}publicListNodemrege(int left,int right,ListNode[] lists){if(left > right)returnnull;if(left == right)return lists[left];//分：分成两个区间int mid =(left + right)/2;ListNode head1 =mrege(left, mid, lists);ListNode head2 =mrege(mid+1, right, lists);//合并两个有序链表returnadd(head1,head2);}publicListNodeadd(ListNode l1,ListNode l2){if(l1 ==null)return l2;if(l2 ==null)return l1;ListNode newHead =newListNode(0);ListNode pre = newHead;while(l1 !=null&& l2 !=null){if(l1.val <= l2.val){ pre.next = l1; pre = pre.next; l1 = l1.next;}else{ pre.next = l2; pre = pre.next; l2 = l2.next;}}if(l1 !=null) pre.next = l1;if(l2 !=null) pre.next = l2;return newHead.next;}}5.3 暴力枚举
解题思路：
- 直接遍历数组，拆分为k-1次合并两个有序链表即可。
//时间复杂度：O(N*K*K)//空间复杂度：O(1)classSolution{publicListNodemergeKLists(ListNode[] lists){if(lists.length ==0)returnnull;ListNode ret = lists[0];for(int i =1; i < lists.length; i++){ ret =add(ret, lists[i]);}return ret;}publicListNodeadd(ListNode l1,ListNode l2){if(l1 ==null)return l2;if(l2 ==null)return l1;ListNode newHead =newListNode(0);ListNode pre = newHead;while(l1 !=null&& l2 !=null){if(l1.val <= l2.val){ pre.next = l1; pre = pre.next; l1 = l1.next;}else{ pre.next = l2; pre = pre.next; l2 = l2.next;}}if(l1 !=null) pre.next = l1;if(l2 !=null) pre.next = l2;return newHead.next;}}六、25.K个⼀组翻转链表
题目链接：25.K个⼀组翻转链表
题目描述：
题目解析：
- 将链表每k个节点逆序，不足k个时不逆序。
解题思路：
- 我们先遍历链表求出节点个数，再除以k得到翻转次数。
- 然后再头插翻转即可。
解题代码：
//时间复杂度：O(n)//空间复杂度：O(1)classSolution{publicListNodereverseKGroup(ListNode head,int k){int n =0;ListNode cur = head;while(cur !=null){ n++; cur = cur.next;} n /= k; cur = head;ListNode ret =newListNode(0);ListNode pre = ret;for(int i =0; i < n; i++){ListNode tmp = cur;for(int j =0; j < k; j++){ListNode next = cur.next; cur.next = pre.next; pre.next = cur; cur = next;} pre = tmp;} pre.next = cur;return ret.next;}}