本节重点：主要包含链表相关算法。
总结：
1、链表翻转是基本操作
- k个一组翻转列表。
3、node.next.next的使用
- 归并排序。
- 判断是否有环
4、交叉链表的第一个节点的快速解法。
4、编码模板
- 需要判断head为null
- 双指针pre和current。一般步长为1，有的时候需要设置步长。
- 新建一个链表，还需要一个tail指针，用来在新链表上追加节点
|
1 2 3 4 5 6 7 8 9 10 11 12 |
public ListNode swapPairs(ListNode head) { // 前置判断 if(head == null){ return null; } // 初始化新链表节点 ListNode result = head; // 定义双指针 ListNode pre = head; ListNode current = head.next; } |
1 链表节点
1、节点定义
|
1 2 3 4 5 6 7 8 |
class ListNode { int val; ListNode next; ListNode(int val) { this.val = val; } } |
2、打印节点
|
1 2 3 4 5 6 7 8 |
public class ListNodePrintUtil { public static void print(ListNode head) { while (head != null) { System.out.println(head.val); head = head.next; } } } |
2 链表翻转
2.1 翻转
反转一个单链表。
示例:
|
1 2 |
输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL |
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list/
算法：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
public ListNode reverseList(ListNode head) { // 1.条件判断 if(head == null || head.next == null){ return head; } // 2.构建新节点 ListNode newHead = head; ListNode current = head.next; // 一定要设置为null head.next = null; // 3.遍历 while(current != null){ ListNode temp = current; current = current.next; temp.next = newHead; newHead = temp; } return newHead; } |
2.2 两两交互链表中元素
算法：
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs
算法：这里使用了tail、pre、current三个指针，注意三个指针在移动过程中设置。
|
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 37 38 |
class Solution { public ListNode swapPairs(ListNode head) { // 1 前置判断 if (head == null || head.next == null) { return head; } // 2.初始化两个节点 ListNode result = null; ListNode tail = null; // 3 定义双指针 ListNode pre = head; ListNode current = head.next; while (current != null) { pre.next = current.next; current.next = pre; if(result==null){ result = current; tail = pre; }else{ // tail tail.next = current; tail = pre; } // 双指针移动 current = pre.next; pre = current; if (current != null) { current = current.next; } } return result; } } |
2.3 K 个一组翻转链表
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例：
给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group
算法：使用步长双指针，按步长截断之后，翻转，再拼接到新的链表上
|
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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
class Solution { // 按步长截断之后，翻转，再拼接到新的链表上 public ListNode reverseKGroup(ListNode head, int k) { // 1.前置校验 if(head == null || head.next ==null || k<=1){ return head; } // 2.初始化节点 ListNode newHead = null; ListNode tail = null; ListNode current = head; ListNode pre = head; // 3.遍历 while(current !=null ){ int step =1; while(step<k && current!=null){ current = current.next; step++; } if(current == null){ break; } // 3.1截断成新的链表，进行倒排 ListNode preTemp = pre; ListNode currentTemp =current; // 设置下次循环起点 current =current.next; pre = current; currentTemp.next =null; // 截断链表 ListNode reverNode = reverseList(preTemp); // 3.2拼接。 if(newHead == null){ newHead = reverNode; tail = preTemp; }else{ tail.next = reverNode; tail = preTemp; } } // 4.连接剩下的节点 if(tail == null){ return pre; } tail.next = pre; return newHead; } public ListNode reverseList(ListNode head) { // 1.条件判断 if(head == null || head.next == null){ return head; } // 2.构建新节点 ListNode newHead = head; ListNode current = head.next; // 一定要设置为null head.next = null; // 3.遍历 while(current != null){ ListNode temp = current; current = current.next; temp.next = newHead; newHead = temp; } return newHead; } } |
2.4 指定M到N的节点翻转
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
算法：查找m和n的位置切分为三个链表，然后翻转m到n链表，再和原来表进行拼装。
|
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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { // 前置 if(m==n || head ==null || head.next == null){ return head; } // 记录四个指针 ListNode p1= null; ListNode p2 =null; ListNode rh = null; ListNode rt = null; // 记录需要翻转的节点 int index = 1; ListNode current = head; while(current != null){ if(index == m-1){ p1 = current; }else if(index == m){ rh = current; } else if(index == n){ rt= current; p2 = current.next; break; } current = current.next; index++; } // 翻转完成之后处理 rt.next = null; //必须设置为null ListNode rnode = reverseList(rh); rh.next = p2; if(p1 == null){ return rnode; }else{ p1.next = rnode; return head; } } public ListNode reverseList(ListNode head) { if (null == head) { return null; } // 1.初始化 ListNode reversNode = head; ListNode temp = head.next; head.next = null; // 2.循环 while (temp != null) { ListNode next = temp.next; temp.next = reversNode; reversNode = temp; temp = next; } return reversNode; } } |
2.5 旋转K个元素
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-list
算法：
- 旋转过程可以理解为：从k+1的位置拆分成两个链表，再拼接。
|
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 |
class Solution { public ListNode rotateRight(ListNode head, int k) { if(head==null || head.next == null){ return head; } int length = 0; ListNode current = head; ListNode tail = head; while(current !=null){ tail = current; current = current.next; length++; } int postion = k % length; if(postion == 0){ return head; } current = head; // 确定拆分表的位置 postion = length - postion +1; ListNode pre = head; while(postion>1){ pre = current; current= current.next; postion --; } pre.next = null; tail.next = head; return current; } } |
3 排序
3.1 链表进行插入排序
对链表进行插入排序。https://leetcode-cn.com/problems/insertion-sort-list/
算法：
- 判断head是否为null
- 排序insert函数要有返回类型，不能是void.
- 每个节点进行插入排序时，需要设置next指针为null
|
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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode insertionSortList(ListNode head) { if(head==null){ return head; } ListNode current = head.next; ListNode resultHead = head; // next为null resultHead.next = null; while(current != null){ ListNode temp = current; current = current.next; // next要设置为null temp.next = null; // 需要根据返回结果，重新设置head resultHead = insert(resultHead,temp); } return resultHead; } // 要有返回类型 private ListNode insert(ListNode resultHead,ListNode node){ ListNode pre = resultHead; if(node.val<=resultHead.val){ node.next = resultHead; resultHead = node; return resultHead; } ListNode current = resultHead.next; if(current==null){ resultHead.next = node; } while(current !=null){ if(current.val>=node.val){ node.next = current; pre.next = node; return resultHead; }else{ pre = current; current = current.next; } } // 如果排序是最后一个元素 pre.next = node; return resultHead; } } |
3.2 输出奇偶排序链
原始链表：5 -> -3 -> 6 -> 2 -> 4
输出：
奇数链表 -3 -> 5
偶数链表 2 -> 4 -> 6
算法：使用 链表的插入排序。
代码：
- 判断head是否为null
- 奇数判断，if (node.val % 2 != 0)，不能是if (node.val % 2 == 1)。
- insert()逻辑中添加了 初始化时这个节点为null 情况。
|
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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
public class JOInsertSort { public void insertionSortList(ListNode head) { if (head == null) { return; } ListNode current = head; ListNode jNode = null; ListNode oNode = null; while (current != null) { ListNode node = current; current = current.next; node.next = null; // 奇数判断 if (node.val % 2 != 0) { jNode = insert(jNode, node); } else { oNode = insert(oNode, node); } } // 输出 ListNodePrintUtil.print(jNode); ListNodePrintUtil.print(oNode); } // 要有返回类型 private ListNode insert(ListNode resultHead, ListNode node) { // 初始化时这个节点为null if (resultHead == null) { resultHead = node; return resultHead; } ListNode pre = resultHead; if (node.val <= resultHead.val) { node.next = resultHead; resultHead = node; return resultHead; } ListNode current = resultHead.next; if (current == null) { resultHead.next = node; } while (current != null) { if (current.val >= node.val) { node.next = current; pre.next = node; return resultHead; } else { pre = current; current = current.next; } } // 如果排序是最后一个元素 pre.next = node; return resultHead; } public static void main(String[] args) { ListNode node1 = new ListNode(5); ListNode node2 = new ListNode(-3); node1.next = node2; ListNode node3 = new ListNode(6); node2.next = node3; ListNode node4 = new ListNode(2); node3.next = node4; ListNode node5 = new ListNode(4); node4.next = node5; JOInsertSort insertSort = new JOInsertSort(); insertSort.insertionSortList(node1); } } |
3.3 归并排序O(n log n)
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
链接：https://leetcode-cn.com/problems/sort-list/
算法思想：
- 分割。通过next.next指针操作实现了查找数组mid的操作。
- 中止条件 current !=null && current.next != null
- pre=pre.next执行条件是current !=null && current.next != null
|
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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
class Solution { public ListNode sortList(ListNode head) { return mergeSort(head); } public ListNode mergeSort(ListNode head){ // 中止条件 if(head == null || head.next ==null){ return head; } // 查找二分节点。使用next.next。 ListNode pre = head; ListNode current = head; while(current !=null && current.next != null){ current = current.next; if(current!=null && current.next != null){ current = current.next; pre=pre.next; }else{ break; } } // 递归 ListNode temp = pre.next; pre.next = null; ListNode left = mergeSort(head); ListNode right = mergeSort(temp); return merge(left,right); } private ListNode merge(ListNode l1,ListNode l2){ if(l1 == null && l2==null){ return null; } // 新建链表需要定义tail ListNode result = null; ListNode tail = null; while(l1!=null || l2!=null){ int left = Integer.MAX_VALUE; int right = Integer.MAX_VALUE; if(l1 != null){ left = l1.val; } if(l2 !=null){ right = l2.val; } if(left <= right){ if(result == null){ result = l1; tail = result; } else{ tail.next= l1; tail = tail.next; } l1 = l1.next; tail.next = null; } else{ if(result == null){ result = l2; tail = result; } else{ tail.next= l2; tail = tail.next; } l2 = l2.next; tail.next = null; } } return result; } } |
4 对折链表
4.1 对折之后打印（从右到左）
给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reorder-list
|
1 |
给定链表 1->2->3->4, 重新排列为 1->4->2->3. |
算法：
- 判断head是否为null
- 将链表转换为list，然后两个指针输出。
- 采用count的作为中止条件，不需要再比较left和right指针了
|
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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
class Solution { public void reorderList(ListNode head) { if (head == null || head.next == null) { return ; } // 1.获取节点数组 List<ListNode> nodeList = new ArrayList<ListNode>(); while (head != null) { nodeList.add(head); head = head.next; } // 2.数组操作 ListNode result = null; int count = nodeList.size(); int right = count - 1; int left = 0; while (true) { if(result==null){ result = nodeList.get(left); }else{ ListNode ltemp = nodeList.get(left); ltemp.next = null; result.next = ltemp; result=ltemp; } left++; count --; if(count<1){ break; } ListNode rtemp = nodeList.get(right); rtemp.next = null; result.next = rtemp; result=rtemp; right--; count --; if(count<1){ break; } } head = nodeList.get(0); return ; } } |
4.2 对折之后打印 (从左到有)
链表从中间对折后左右依次打印，效果:
1->2->3->4->5
3 2 4 1 5
算法：
- 判断head是否为null
- 将链表转换为list，然后两个指针输出。
- 采用count的作为中止条件，不需要再比较left和right指针了
|
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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
public class DuiZheList { public ListNode process(ListNode head) { if (head == null || head.next == null) { return head; } // 1.获取节点数组 List<ListNode> nodeList = new ArrayList<ListNode>(); while (head != null) { nodeList.add(head); head = head.next; } // 2.数组操作 ListNode result = null; int count = nodeList.size(); int right = count - 1; int left = 0; while (true) { if (result == null) { result = nodeList.get(right); } else { ListNode rtemp = nodeList.get(right); rtemp.next = result; result = rtemp; } right--; count--; if (count < 1) { break; } ListNode ltemp = nodeList.get(left); ltemp.next = result; result = ltemp; left++; count--; if (count < 1) { break; } } return result; } public static void main(String[] args) { ListNode node1 = new ListNode(1); ListNode node2 = new ListNode(2); node1.next = node2; ListNode node3 = new ListNode(3); node2.next = node3; ListNode node4 = new ListNode(4); node3.next = node4; ListNode node5 = new ListNode(5); node4.next = node5; DuiZheList duiZheList = new DuiZheList(); ListNodePrintUtil.print(duiZheList.process(node1)); } } |
5 链表删除节点
5.1 删除指定点
删除链表中等于给定值 val 的所有节点。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-linked-list-elements/
示例:
|
1 2 |
<strong>输入:</strong> 1->2->6->3->4->5->6, <em><strong>val</strong></em> = 6 <strong>输出:</strong> 1->2->3->4->5 |
算法：
- 判断head是否为null
- 最后再处理head节点。
|
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 |
class Solution { public ListNode removeElements(ListNode head, int val) { // 判断为空 if(head == null){ return null; } // 设置前后指针 ListNode pre = head; ListNode current = head.next; while(current !=null ){ if(current.val == val){ pre.next = current.next; current = current.next; }else{ pre = current; current = current.next; } } // 还需要判断head。需要考虑所有节点都为null情况 if(head.val == val){ head = head.next; } return head; } } |
5.2 通过值拷贝删除
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。
输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/delete-node-in-a-linked-list
算法：因为无法获取node的pre指针，通过值拷贝来实现。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Solution { // 因为无法获取node的pre指针，通过值拷贝来实现。 public void deleteNode(ListNode node) { if(node.next == null || node == null){ return; } ListNode current = node.next; ListNode pre = node; while(current.next !=null){ pre.val = current.val; pre = current; current = current.next; } // 结束之后 pre.val = current.val; pre.next = null; return; } } |
6 遍历节点
6.1 倒数第k个节点
6.1.1 输出导出第K个节点
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof
算法：使用双指针，两个指针针步长为k。
|
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 |
class Solution { public ListNode getKthFromEnd(ListNode head, int k) { if(head == null){ return head; } ListNode pre= head; ListNode current= head.next; int step = 1; while(current != null){ if(step==k){ break; } current = current.next; step++; } // 不足k个节点输出所有节点 if(step<k){ return pre; } // 移动双指针 while(current !=null ){ pre = pre.next; current = current.next; } return pre; } } |
6.1.2 删除倒数第K个节点
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
算法：
- 需要考虑是head节点情况。
|
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 37 38 39 40 |
class Solution { public ListNode removeNthFromEnd(ListNode head, int k) { if(head == null || k<=0){ return head; } ListNode current= head.next; int step = 1; while(current != null){ if(step==k){ break; } current = current.next; step++; } // 不足k个节点输出所有节点 if(step<k){ return head; } // 移动双指针 ListNode pre= head; ListNode prePre = null; while(current !=null ){ prePre = pre; pre = pre.next; current = current.next; } // 考虑是head情况 if(prePre ==null){ head = head.next; }else{ prePre.next=pre.next; } return head; } } |
6.2 环
6.2.1 是否存环
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-cycle
解法1 双指针next.next
算法：通过两个指针来实现，一个步长是node.next。一个是node.next.next。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
public class Solution { public boolean hasCycle(ListNode head) { if(head == null || head.next==null){ return false; } ListNode pre = head; ListNode current = head; while (current !=null){ pre = pre.next; current = current.next; if(current!=null){ current = current.next; } if(pre == current){ return true; } } return false; } } |
解法2 通过HashSet记录访问节点
|
1 2 3 4 5 6 7 8 9 10 11 |
public boolean checkWithSet(ListNode head){ Set<ListNode> dic = new HashSet<ListNode>(); while(head !=null){ if(dic.contains(head)){ return true; } dic.add(head); head = head.next; } return false; } |
6.2.2 查找环第一个节点
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-cycle-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
算法：通过map保存节点路径信息。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
public class Solution { // 算法：使用Set保存 public ListNode detectCycle(ListNode head) { Map<ListNode,Integer> dic = new HashMap<ListNode,Integer>(); ListNode current = head; int index =0; while(current != null){ if(dic.containsKey(current)){ return current; } dic.put(current,index); index++; current = current.next; } return null; } } |
6.3 链表交叉
6.3.1 两个链表第一个交点
输入两个链表，找出它们的第一个公共节点。
链接：https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/
解法1 ：借助于set来完成
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { Set<ListNode> dic = new HashSet<ListNode>(); while(headA !=null || headB!=null){ if(headA != null){ if(dic.contains(headA)){ return headA; }else{ dic.add(headA); headA=headA.next; } } if(headB != null){ if(dic.contains(headB)){ return headB; }else{ dic.add(headB); headB=headB.next; } } } return null; } } |
解法2 路径相等
|
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 |
/** * 算法：执行到末尾节点，切换到对应的链表，执行循环操作。最终两个节点遍历路径是一样的。 * 如果没有交点，则什么时候中止？最后都指向了同一个 null （None）节点。 * 如果有交点，则到交点的路径是一样的。 **/ public ListNode getQuickIntersectionNode(ListNode headA, ListNode headB) { // 初始化 ListNode node1 = headA; ListNode node2 = headB; // 中止条件 while (node1 != node2) { if(node1 !=null ){ node1=node1.next; }else{ node1 = headB; } if(node2 !=null ){ node2=node2.next; }else{ node2 = headA; } } return node1; } |
7 合并链表
7.1 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
算法：
- 新节点需要初始化下
|
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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { // 前置判断 if(l1 ==null && l2==null){ return null; } if(l1 == null ){ return l2; } if(l2 == null){ return l1; } // 初始化新节点 ListNode result=null; if(l1.val<l2.val){ result = l1; l1=l1.next; result.next = null; }else{ result = l2; l2=l2.next; result.next = null; } ListNode tail = result; // 构造 while(l1 !=null || l2!=null){ if(l1!=null && l2 !=null){ if(l1.val < l2.val){ tail.next = l1; l1 = l1.next; tail = tail.next; tail.next = null; }else{ tail.next = l2; l2 = l2.next; tail = tail.next; tail.next = null; } }else if(l1!=null){ tail.next=l1; // 注意中止条件 break; }else{ tail.next =l2; // 注意中止条件 break; } } return result; } } |
7.2 合并k个有序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-k-sorted-lists
算法：使用归并处理，分而治之。使用了7.1合并两个有序链表操作
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Solution { public ListNode mergeKLists(ListNode[] lists) { if(lists==null || lists.length ==0){ return null; } return mergeSort(lists,0,lists.length-1); } public ListNode mergeSort(ListNode[] lists,int beg,int end){ if(beg == end){ return lists[beg]; } int mid = (beg+end)/2; ListNode left = mergeSort(lists,beg,mid); ListNode right = mergeSort(lists,mid+1,end); return mergeTwoLists(left,right); } public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 参考7.1节代码 } } |
8 运算
8.1 两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
代码：
- 新建一个链表时，需要定义一个head和tail。tail在追加操作时使用
- 注意while条件
|
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 37 38 39 40 41 42 43 44 |
class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { if(l1 == null && l2==null){ throw new RuntimeException("l1&l2 is null"); } else if(l1==null){ return l2; }else if(l2 == null){ return l1; } int carry = 0; // 定义一个新的列表时候,需要定义一个result,作为head,还需要定义一个tail节点 ListNode result=null; ListNode tail = null; while (l1!=null || l2!=null || carry>0){ int leftval = 0; if(l1 !=null){ leftval = l1.val; l1=l1.next; } int rightval = 0; if(l2 !=null){ rightval = l2.val; l2 = l2.next; } int sum = leftval + rightval + carry; carry = sum/10; if(result==null){ result = new ListNode(sum%10); tail = result; }else{ // 移动tail tail.next = new ListNode(sum%10); tail = tail.next; } } return result; } } |
8.2 两数求和
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers-ii
算法：首先翻转两个输入链表（2.1） ；然后利用8.1两个数之和； 翻转结果。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { l1=reverseList(l1); l2=reverseList(l2); ListNode result = addReverseTwoNumbers(l1,l2); return reverseList(result); } public ListNode addReverseTwoNumbers(ListNode l1, ListNode l2) { =8.1 求和= } public ListNode reverseList(ListNode head) { =2.1 翻转链表= } } |
