链表问题
面试链表解题的方法论
- 对于笔试，不用太在乎空间复杂度，一切为了时间复杂度
- 对于面试，时间复杂度依然放在第一位，但是一定要找到空间最省的方法
链表面试题常用数据结构和技巧
- 使用容器（哈希表、数组等）
- 快慢指针
快慢指针
- 输入链表头节点，奇数长度返回中点，偶数长度返回上中点
- 输入链表头节点，奇数长度返回中点，偶数长度返回下中点
- 输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
- 输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个
package com.harrison.six; import java.util.ArrayList; public class Code01_LinkedListMid { public static class Node { public int value; public Node next; public Node(int v) { value = v; } } // 奇数长度返回中点，偶数长度返回上中点 public static Node midOrUpMidNode(Node head) { if (head == null || head.next == null || head.next.next == null) { return head; } // 代表链表有三个或三个以上节点 Node slow = head.next; Node fast = head.next.next; while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } // 奇数长度返回中点，偶数长度返回下中点 public static Node midOrDownMidNode(Node head) { if (head == null || head.next == null) { return head; } Node slow = head.next; Node fast = head.next; while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } // 奇数长度返回中点前一个，偶数长度返回上中点前一个 public static Node midOrUpMidPreNode(Node head) { if (head == null || head.next == null || head.next.next == null) { return head; } // 代表链表有三个或三个以上节点 Node slow = head; Node fast = head.next.next; while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } // 奇数长度返回中点前一个，偶数长度返回下中点前一个 public static Node midOrDownMidPreNode(Node head) { if (head == null || head.next == null) { return null; } if (head.next.next == null) { return head; } Node slow = head; Node fast = head.next; while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } public static Node right1(Node head) { if (head == null) { return null; } Node cur = head; ArrayList<Node> arr = new ArrayList<>(); while (cur != null) { arr.add(cur); cur = cur.next; } return arr.get((arr.size() - 1) / 2); } public static Node right2(Node head) { if (head == null) { return null; } Node cur = head; ArrayList<Node> arr = new ArrayList<>(); while (cur != null) { arr.add(cur); cur = cur.next; } return arr.get(arr.size() / 2); } public static Node right3(Node head) { if (head == null || head.next == null || head.next.next == null) { return null; } Node cur = head; ArrayList<Node> arr = new ArrayList<>(); while (cur != null) { arr.add(cur); cur = cur.next; } return arr.get((arr.size() - 3) / 2); } public static Node right4(Node head) { if (head == null || head.next == null) { return null; } Node cur = head; ArrayList<Node> arr = new ArrayList<>(); while (cur != null) { arr.add(cur); cur = cur.next; } return arr.get((arr.size() - 2) / 2); } public static void main(String[] args) { Node test = null; test = new Node(0); test.next = new Node(1); test.next.next = new Node(2); test.next.next.next = new Node(3); test.next.next.next.next = new Node(4); test.next.next.next.next.next = new Node(5); test.next.next.next.next.next.next = new Node(6); test.next.next.next.next.next.next.next = new Node(7); test.next.next.next.next.next.next.next.next = new Node(8); Node ans1 = null; Node ans2 = null; ans1 = midOrUpMidNode(test); ans2 = right1(test); System.out.println(ans1 != null ? ans1.value : "无"); System.out.println(ans2 != null ? ans2.value : "无"); ans1 = midOrDownMidNode(test); ans2 = right2(test); System.out.println(ans1 != null ? ans1.value : "无"); System.out.println(ans2 != null ? ans2.value : "无"); ans1 = midOrUpMidPreNode(test); ans2 = right3(test); System.out.println(ans1 != null ? ans1.value : "无"); System.out.println(ans2 != null ? ans2.value : "无"); ans1 = midOrDownMidPreNode(test); ans2 = right4(test); System.out.println(ans1 != null ? ans1.value : "无"); System.out.println(ans2 != null ? ans2.value : "无"); } }
常见面试题
给定一个单链表的头节点head，请判断该链表是否为回文结构。
- 栈方法特别简单（笔试用）
- 改原链表的方法就需要注意边界了（面试用）
package com.harrison.six; import java.util.Stack; public class Code02_PalindromeList { public static class Node { public int value; public Node next; public Node(int v) { value = v; } } // need n extra space public static boolean isPalindrome1(Node head) { Stack<Node> stack = new Stack<Node>(); Node cur = head; while (cur != null) { stack.push(cur); cur = cur.next; } while (head != null) { if (head.value != stack.pop().value) { return false; } head = head.next; } return true; } // need n/2 extra space public static boolean isPalindrome2(Node head) { if (head == null || head.next == null) { return true; } Node right = head.next; Node cur = head; while (cur.next != null && cur.next.next != null) { right = right.next; cur = cur.next.next; } Stack<Node> stack = new Stack<Node>(); while (right != null) { stack.push(right); right = right.next; } while (!stack.isEmpty()) { if (head.value != stack.pop().value) { return false; } head = head.next; } return true; } // need O(1) extra space public static boolean isPalindrome3(Node head) { if (head == null || head.next == null) { return true; } Node n1 = head; Node n2 = head; while (n2.next != null && n2.next.next != null) {// find mid node n1 = n1.next;// n1->mid n2 = n2.next.next;// n2-> end } // 奇数个n1来到中点，偶数个n1来到上中点 n2 = n1.next;// n2 -> right part first node n1.next = null;// mid.next -> null Node n3 = null; while (n2 != null) {// right part convert n3 = n2.next;// n3-> save next node n2.next = n1;// next of right node convert n1 = n2;// n1 move n2 = n3;// n2 move } n3 = n1;// n3-> save last node n2 = head;// n2-> left first node boolean res = true; while (n1 != null && n2 != null) {// check palindrome if (n1.value != n2.value) { res = false; break; } n1 = n1.next;// left to mid n2 = n2.next;// right to mid } n1 = n3.next; n3.next = null; while (n1 != null) {// recover list n2 = n1.next; n1.next = n3; n3 = n1; n1 = n2; } return res; } public static void printLinkedList(Node node) { System.out.print("Linked List："); while (node != null) { System.out.print(node.value + " "); node = node.next; } System.out.println(); } public static void main(String[] args) { Node head = null; printLinkedList(head); System.out.print(isPalindrome1(head)+ " | "); System.out.print(isPalindrome2(head)+ " | "); System.out.print(isPalindrome3(head)+ " | "); printLinkedList(head); System.out.println("======================="); head = new Node(1); printLinkedList(head); System.out.print(isPalindrome1(head)+ " | "); System.out.print(isPalindrome2(head)+ " | "); System.out.print(isPalindrome3(head)+ " | "); printLinkedList(head); System.out.println("======================="); head = new Node(1); head.next = new Node(2); printLinkedList(head); System.out.print(isPalindrome1(head)+ " | "); System.out.print(isPalindrome2(head)+ " | "); System.out.print(isPalindrome3(head)+ " | "); printLinkedList(head); System.out.println("======================="); head = new Node(1); head.next = new Node(1); printLinkedList(head); System.out.print(isPalindrome1(head) + " | "); System.out.print(isPalindrome2(head) + " | "); System.out.println(isPalindrome3(head) + " | "); printLinkedList(head); System.out.println("========================="); head = new Node(1); head.next = new Node(2); head.next.next = new Node(3); printLinkedList(head); System.out.print(isPalindrome1(head) + " | "); System.out.print(isPalindrome2(head) + " | "); System.out.println(isPalindrome3(head) + " | "); printLinkedList(head); System.out.println("========================="); head = new Node(1); head.next = new Node(2); head.next.next = new Node(1); printLinkedList(head); System.out.print(isPalindrome1(head) + " | "); System.out.print(isPalindrome2(head) + " | "); System.out.println(isPalindrome3(head) + " | "); printLinkedList(head); System.out.println("========================="); head = new Node(1); head.next = new Node(2); head.next.next = new Node(3); head.next.next.next = new Node(1); printLinkedList(head); System.out.print(isPalindrome1(head) + " | "); System.out.print(isPalindrome2(head) + " | "); System.out.println(isPalindrome3(head) + " | "); printLinkedList(head); System.out.println("========================="); head = new Node(1); head.next = new Node(2); head.next.next = new Node(2); head.next.next.next = new Node(1); printLinkedList(head); System.out.print(isPalindrome1(head) + " | "); System.out.print(isPalindrome2(head) + " | "); System.out.println(isPalindrome3(head) + " | "); printLinkedList(head); System.out.println("========================="); head = new Node(1); head.next = new Node(2); head.next.next = new Node(3); head.next.next.next = new Node(2); head.next.next.next.next = new Node(1); printLinkedList(head); System.out.print(isPalindrome1(head) + " | "); System.out.print(isPalindrome2(head) + " | "); System.out.println(isPalindrome3(head) + " | "); printLinkedList(head); System.out.println("========================="); } }
将单向链表按某值划分成左边小、中间相等、右边大的形式
- 把链表放入数组里，在数组上做partition（笔试用）
- 分成小、中、大三部分，再把各个部分之间串起来（面试用）
package com.harrison.six; public class Code03_SmallerEqualBigger { public static class Node{ public int value; public Node next; public Node(int v) { value=v; } } public static void swap(Node [] nodeArr,int a,int b) { Node tmpNode=nodeArr[a]; nodeArr[a]=nodeArr[b]; nodeArr[b]=tmpNode; } public static void arrPartition(Node[] nodeArr,int pivot) { int small=-1; int big=nodeArr.length; int index=0; while(index!=big) { if(nodeArr[index].value<pivot) { swap(nodeArr, ++small, index++); }else if(nodeArr[index].value==pivot) { index++; }else { swap(nodeArr, --big, index); } } } public static Node listPartition1(Node head,int pivot) { if(head==null) { return head; } Node cur=head; int i=0; while(cur!=null) { i++; cur=cur.next; } Node[] nodeArr=new Node[i]; i=0; cur=head; for(i=0; i!=nodeArr.length; i++) { nodeArr[i]=cur; cur=cur.next; } arrPartition(nodeArr, pivot); for(i=1; i!=nodeArr.length; i++) { nodeArr[i-1].next=nodeArr[i]; } nodeArr[i-1]=null; return nodeArr[0]; } public static Node listPartition2(Node head,int pivot) { Node sH=null;//小于区的头 Node sT=null;//小于区的尾 Node eH=null;//等于区的头 Node eT=null;//等于区的尾 Node bH=null;//大于区的头 Node bT=null;//大于区的尾 Node next=null;//save next node while(head!=null) { next=head.next; head.next=null; if(head.value<pivot) { if(sH==null) { sH=head; sT=head; }else { sT.next=head; sT=head; } }else if(head.value==pivot) { if(eH==null) { eH=head; eT=head; }else { eT.next=head; eT=head; } }else { if(bH==null) { bH=head; bT=head; }else { bT.next=head; bT=head; } } head=next; } // 小于区域的尾巴，连等于区域的头，等于区域的尾巴连大于区域的头 if(sT!=null) {//如果有小于区域 sT.next=eH; eT=eT==null?sT:eT;//谁去连大于区域的头，谁就变成等于区域的头eT } if(eT!=null) { eT.next=bH; } return sH!=null?sH:(eH!=null?eH:bH); } public static void printLinkedList(Node node) { System.out.print("Linked List："); while(node!=null) { System.out.print(node.value+" "); node=node.next; } System.out.println(); } public static void main(String[] args) { Node head1=new Node(7); head1.next=new Node(9); head1.next.next=new Node(1); head1.next.next.next = new Node(8); head1.next.next.next.next = new Node(5); head1.next.next.next.next.next = new Node(2); head1.next.next.next.next.next.next = new Node(5); printLinkedList(head1); head1=listPartition2(head1, 5); printLinkedList(head1); } }
一种特殊的单链表节点类型描述如下：
class Node{ int value; Node next; Node rand; Node(int val){ value=val; } }
rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，也可能指向null。给定一个由Node节点类型组成的无环单链表的头节点head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。要求：时间复杂度O(N)，额外空间复杂度O(1)
package com.harrison.six; import java.util.HashMap; public class Code04_CopyListWithRandom { public static class Node { int value; Node next; Node rand; Node(int val) { value = val; } } public static Node copyRandomList1(Node head) { // key 老节点 value 新节点 HashMap<Node, Node> map = new HashMap<Node, Node>(); Node cur = head; while (cur != null) { map.put(cur, new Node(cur.value)); cur = cur.next; } cur = head; while (cur != null) { // cur 老 // map.get(cur) 新 // 新.next -> cur.next克隆节点找到 map.get(cur).next = map.get(cur.next); map.get(cur).rand = map.get(cur.rand); cur = cur.next; } return map.get(head); } public static Node copyRandomList2(Node head) { if (head == null) { return null; } Node cur = head; Node next = null; // copy node and link to every node // 1 -> 2 -> 3 -> null // 1 -> 1' -> 2 -> 2' -> 3 -> 3' while (cur != null) { // cur 老 next 老的下一个 next = cur.next; cur.next = new Node(cur.value); cur.next.next = next; cur = next; } cur = head; Node curCopy = null; // set curCopy node rand while (cur != null) { next = cur.next.next; curCopy = cur.next; curCopy.rand = cur.rand != null ? cur.rand.next : null; cur = next; } Node res = head.next; cur = head; // split next方向上，把新老链表分离，不用动rand指针 while (cur != null) { next = cur.next.next; curCopy = cur.next; cur.next = next; curCopy.next = next != null ? next.next : null; cur = next; } return res; } public static void printLinkedList(Node node) { System.out.print("Linked List："); while (node != null) { System.out.print(node.value + " "); node = node.next; } System.out.println(); } public static void main(String[] args) { Node head1=new Node(7); head1.next=new Node(9); head1.next.next=new Node(1); head1.next.next.next = new Node(8); head1.next.next.next.next = new Node(5); head1.next.next.next.next.next = new Node(2); head1.next.next.next.next.next.next = new Node(5); printLinkedList(head1); //head1=copyRandomList1(head1); head1=copyRandomList2(head1); printLinkedList(head1); } }
给定两个可能有环也可能无环的单链表，头节点head1和head2。请实现一个函数，如果两个链表相交，请返回相交的第一个节点。如果不相交，返回null。【要求】：如果两个链表长度之和为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)。
- 给你一个链表，返回第一个入环的节点
- 两个无环链表相交，返回第一个相交节点
- 两个有环链表相交，返回第一个相交节点
package com.harrison.six; public class Code05_FindFirstIntesectNode { public static class Node { public int value; public Node next; public Node(int v) { value = v; } } // 找到链表第一个入环节点，如果无环，返回null public static Node getLoopNode(Node head) { if (head == null || head.next == null || head.next.next == null) { return null; } // n1 慢指针 n2 快指针 Node n1 = head.next; Node n2 = head.next.next; while (n1 != n2) { if (n2.next == null || n2.next.next == null) { return null; } n2 = n2.next.next; n1 = n1.next; } n2 = head;// n2 -> walk again form head // n1位置不变 while (n1 != n2) { n1 = n1.next; n2 = n2.next; } return n1; } // 如果两个链表都无环，返回第一个相交节点，如果不相交，返回null public static Node noLoop(Node head1, Node head2) { if (head1 == null || head2 == null) { return null; } Node cur1 = head1; Node cur2 = head2; int n = 0; // n>0 cur1长 n<0 cur2长 n==0 一样长 while (cur1.next != null) { n++; cur1 = cur1.next; } while (cur2.next != null) { n--; cur2 = cur2.next; } // 结束两个while循环后，两个链表的当前节点分别来到了end1和end2 // 如果end1!=end2，说明没有共用一块内存地址，两个链表必不相交 if (cur1 != cur2) { return null; } // n 链表1减去链表2的长度 cur1 = n > 0 ? head1 : head2;// 谁长，谁的头变成cur1 cur2 = cur1 == head1 ? head2 : head1;// 谁短，谁的头变成cur2 n = Math.abs(n); /** * 长的链表先把多的节点先走完，然后两条链表一起走 因为此时两条链表长度一样且公共部分也一样长 所以，必然会在第一个相交的节点处相遇 */ while (n != 0) { n--; cur1 = cur1.next; } while (cur1 != cur2) { cur1 = cur1.next; cur2 = cur2.next; } return cur1; } // 两个有环链表，返回第一个相交节点，如果不想相交返回null // 两个有环链表相交，则一定公用同一个环！！！ public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) { Node cur1 = null; Node cur2 = null; // 如果两个链表第一个相交节点相等，则不用考虑共同的环，且loop1和loop2成为end1和end2 if (loop1 == loop2) { cur1 = head1; cur2 = head2; int n = 0; while (cur1 != loop1) { n++; cur1 = cur1.next; } while (cur2 != loop2) { n--; cur2 = cur2.next; } if (cur1 != cur2) { return null; } cur1 = n > 0 ? head1 : head2; cur2 = cur1 == head1 ? head2 : head1; n = Math.abs(n); while (n != 0) { n--; cur1 = cur1.next; } while (cur1 != cur2) { cur1 = cur1.next; cur2 = cur2.next; } return cur1; } else { cur1 = loop1.next; while (cur1 != loop1) { if (cur1 == loop2) { return loop1; } cur1 = cur1.next; } return null; } } public static Node getIntersectNode(Node head1, Node head2) { if (head1 == null || head2 == null) { return null; } Node loop1 = getLoopNode(head1); Node loop2 = getLoopNode(head2); if (loop1 == null && loop2 == null) { return noLoop(head1, head2); } if (loop1 != null && loop2 != null) { return bothLoop(head1, loop1, head2, loop2); } return null; } public static void main(String[] args) { // 1->2->3->4->5->6->7->null Node head1 = new Node(1); head1.next = new Node(2); head1.next.next = new Node(3); head1.next.next.next = new Node(4); head1.next.next.next.next = new Node(5); head1.next.next.next.next.next = new Node(6); head1.next.next.next.next.next.next = new Node(7); // 0->9->8->6->7->null Node head2 = new Node(0); head2.next = new Node(9); head2.next.next = new Node(8); head2.next.next.next = head1.next.next.next.next.next; // 8->6 System.out.println(getIntersectNode(head1, head2).value); // 1->2->3->4->5->6->7->4... head1 = new Node(1); head1.next = new Node(2); head1.next.next = new Node(3); head1.next.next.next = new Node(4); head1.next.next.next.next = new Node(5); head1.next.next.next.next.next = new Node(6); head1.next.next.next.next.next.next = new Node(7); head1.next.next.next.next.next.next = head1.next.next.next; // 7->4 // 0->9->8->2... head2 = new Node(0); head2.next = new Node(9); head2.next.next = new Node(8); head2.next.next.next = head1.next; // 8->2 System.out.println(getIntersectNode(head1, head2).value); // 0->9->8->6->4->5->6.. head2 = new Node(0); head2.next = new Node(9); head2.next.next = new Node(8); head2.next.next.next = head1.next.next.next.next.next; // 8->6 System.out.println(getIntersectNode(head1, head2).value); } }
能不能不给单链表的头节点，只给想要删除的节点，就能做到在链表上把这个点删掉？
可以，将要删除节点的下一个节点的值覆盖要删除节点的值，然后将要删除节点的next指针指向下下个节点。
缺点：事实上，没把想要删除的节点删掉，只是把下一个节点盖到了自己身上，删掉的其实是下一个节点。
- 节点是服务器
- 节点内容很复杂，连拷贝函数和构造函数都不能调用，那么无法完成值的覆盖
- 【最严重】无法删除链表最后一个节点
