package y2019.Algorithm.LinkedList.medium; import y2019.Algorithm.LinkedList.ListNode; /** * @ProjectName: cutter-point * @Package: y2019.Algorithm.LinkedList.medium * @ClassName: AddTwoNumbers * @Author: xiaof * @Description: TODO 2. Add Two Numbers * You are given two non-empty linked lists representing two non-negative integers. * The digits are stored in reverse order and each of their nodes contain a single digit. * Add the two numbers and return it as a linked list. * You may assume the two numbers do not contain any leading zero, except the number 0 itself. * * Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) * Output: 7 -> 0 -> 8 * Explanation: 342 + 465 = 807. * @Date: 2019/8/1 9:06 * @Version: 1.0 */ public class AddTwoNumbers { public ListNode solution(ListNode l1, ListNode l2) { //两数相加,用链表遍历相加进位即可 int increment = 0; ListNode p1 = l1, p2 = l2, tail1 = p1, tail2 = p2; while (p1 != null && p2 != null) { int curValue = p1.val + p2.val + increment; increment = curValue / 10; curValue = curValue % 10; p1.val = curValue; tail1 = p1; tail2 = p2; p1 = p1.next; p2 = p2.next; } //如果l1比较长 if (p2 == null && p1 != null) { //吧剩下的加入链表 while (p1 != null) { int curValue = p1.val + increment; increment = curValue / 10; curValue = curValue % 10; p1.val = curValue; tail1 = p1; p1 = p1.next; } } if (p1 == null && p2 != null) { //吧剩下的加入链表 while (p2 != null) { int curValue = p2.val + increment; increment = curValue / 10; curValue = curValue % 10; tail1.next = new ListNode(curValue); tail1 = tail1.next; p2 = p2.next; } } //最后添加increment节点 if (increment > 0) { tail1.next = new ListNode(increment); } return l1; } public static void main(String[] args) { ListNode node1 = new ListNode(); node1.val = 9; ListNode node2 = new ListNode(); node2.val = 9; node1.next = node2; ListNode node21 = new ListNode(); AddTwoNumbers fuc = new AddTwoNumbers(); fuc.solution(node1, node21); } }
package y2019.Algorithm.LinkedList.medium; import y2019.Algorithm.LinkedList.Node; /** * @ProjectName: cutter-point * @Package: y2019.Algorithm.LinkedList.medium * @ClassName: CopyRandomList * @Author: xiaof * @Description: TODO 138. Copy List with Random Pointer * A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. * Return a deep copy of the list. * * Input: * {"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1} * * Explanation: * Node 1's value is 1, both of its next and random pointer points to Node 2. * Node 2's value is 2, its next pointer points to null and its random pointer points to itself. * * 思路，参考大神操作 * 1.首先吧链表复制，但是不拆开，复制出来的链表还是连在原来的链表上 * 2.根据上一个节点是下一个节点的原始复制对象，那么只需要吧random相应指向的节点的下一个 * 3.拆开复制的链表 * @Date: 2019/8/1 9:35 * @Version: 1.0 */ public class CopyRandomList { public Node solution(Node head) { if (head == null) return null; //开始复制 Node p = head, p2, newHead, copy; //1 step while (p != null) { //新节点指向原来的下一个节点 Node temp = new Node(p.val, p.next, p.random); //原来旧节点指向新节点 p.next = temp; //移动到下一个旧节点 p = temp.next; } //2 step 修改random指向 p = head; while (p != null) { p2 = p.next; if(p2.random != null) { p2.random = p.random.next;//指向复制的节点 } p = p.next.next; } //3. step拆分链表 p = head; Node nh = new Node(), np1 = nh, np2 = np1; while (p != null) { p2 = p.next.next; np1 = p.next; np2.next = np1; np2 = np1; p.next = p2; p = p2; } return nh.next; } }
package y2019.Algorithm.LinkedList.medium; import y2019.Algorithm.LinkedList.ListNode; import java.util.HashMap; import java.util.Map; /** * @ProjectName: cutter-point * @Package: y2019.Algorithm.LinkedList.medium * @ClassName: DetectCycle * @Author: xiaof * @Description: TODO 142. Linked List Cycle II * Given a linked list, return the node where the cycle begins. If there is no cycle, return null. * To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked * list where tail connects to. If pos is -1, then there is no cycle in the linked list. * * Input: head = [3,2,0,-4], pos = 1 * Output: tail connects to node index 1 * Explanation: There is a cycle in the linked list, where tail connects to the second node. * @Date: 2019/8/1 8:57 * @Version: 1.0 */ public class DetectCycle { public ListNode solution(ListNode head) { //针对有换问题，可以考虑用set，或者用2个指针，如果要找位置的话，感觉hashmap可能更好 Map nodeMap = new HashMap(); ListNode res = null, p = head; int index = 0; //遍历链表，直到遇到重复 while (p != null) { //遍历获取下一个数据 if(nodeMap.containsKey(p)) { //如果已经存在 res = p; break; } else { //如果不包含 nodeMap.put(p, index++); p = p.next; } } return res; } }
package y2019.Algorithm.LinkedList.hard; import y2019.Algorithm.LinkedList.ListNode; /** * @ProjectName: cutter-point * @Package: y2019.Algorithm.LinkedList.hard * @ClassName: MergeKLists * @Author: xiaof * @Description: 23. Merge k Sorted Lists * Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. * Input: * [ * 1->4->5, * 1->3->4, * 2->6 * ] * Output: 1->1->2->3->4->4->5->6 * * 参考： 148. Sort List的解法 * @Date: 2019/8/1 10:28 * @Version: 1.0 */ public class MergeKLists { public ListNode mergeKLists(ListNode[] lists) { //多链表合并,可以简化为多个双链表合并，做循环即可 if (lists == null || lists.length == 0) { return null; } if (lists.length == 1) { return lists[0]; } //1,先取一个数组，然后循环遍历所有数组跟之前的数组做merge ListNode res = lists[0]; for(int i = 1; i < lists.length; ++i) { res = merge(res, lists[i]); } return res; } ListNode merge(ListNode l1, ListNode l2) { if(l1 == null && l2 == null) { return null; } else if (l1 == null) { return l2; } else if (l2 == null) { return l1; } //合并俩个链表 ListNode newl = new ListNode(0); //遍历两个链表，获取对应的位置添加到链表 //1。老规矩，获取前一个链表位置，后一个位置，当前位置 ListNode addl = newl, l1next = l1.next, l2next = l2.next, temp; //2.吧需要添加进去的链表后面加上当前节点 while (l1 != null && l2 != null) { //3.把当前节点的下一个索引断开 if(l1.val < l2.val) { //如果是必第二个链表的小，那么我们用第一个链表 addl.next = l1; temp = l1.next; l1.next = null; l1 = temp; } else { addl.next = l2; temp = l2.next; l2.next = null; l2 = temp; } //4.吧当前索引指向下一个节点 addl = addl.next; } //5.最后吧剩余的节点直接加入到新链表中 if(l1 != null) { addl.next = l1; } if(l2 != null) { addl.next = l2; } return newl.next; } }