链表解题方法论:
- 对于笔试,不用太在乎空间复杂度,一切为了时间复杂度
- 对于面试,时间复杂度第一位,但一定要找到空间最省的方法
链表题目常用数据结构和技巧:
- 使用容器(哈希表、数组)
- 快慢指针
快慢指针练习
- 输入链表头结点,如果奇数长度返回中点,如果偶数长度返回上中点
- 输入链表头结点,如果奇数长度返回中点,如果偶数长度返回下中点
- 输入链表头结点,如果奇数长度返回中点前一个节点,如果偶数长度返回上中点前一个节点
- 输入链表头结点,如果奇数长度返回中点前一个节点,如果偶数长度返回下中点前一个节点
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
| public static class Node { public int value; public Node next;
public Node(int val) { this.value = val; } }
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 null; } 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; }
|
1.判断链表是否是回文结构(LeetCode 234. easy)
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 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103
| public static class Node { public int value; public Node next;
public Node(int val) { this.value = val; } }
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; }
public static boolean isPalindrome2(Node head) { if (head == null || head.next == null) { return true; } Node right = head.next; Node cur = head.next; 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; }
public static boolean isPalindrome3(Node head) { if (head == null || head.next == null) { return true; } Node n1 = head.next; Node n2 = head.next; while (n2.next != null && n2.next.next != null) { n1 = n1.next; n2 = n2.next.next; }
n2 = n1.next; n1.next = null;
Node n3 = null; while (n2 != null) { n3 = n2.next; n2.next = n1; n1 = n2; n2 = n3; }
n3 = n1; n2 = head; boolean res = true; while (n1 != null && n2 != null) { if (n1.value != n2.value) { res = false; break; } n1 = n1.next; n2 = n2.next; }
n1 = n3.next; n3.next = null; while (n1 != null) { n2 = n1.next; n1.next = n3; n3 = n1; n1 = n2; } return res; }
|
另一道题同样的解题思路,找中点,反转链表:
一个链表有偶数个节点,编号L1->L2->L3->L4->R1->R2->R3->R4,要求返回L1->R4->L2->R3->L3->R2->L4->R1
2.按左边小、中间相等、右边大分隔链表(LeetCode 86. medium,相似)
- 把链表放到数组里,在数组上做partition(笔试用)
- 分成小中大三部分,再把各个部分串起来(面试用)
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 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111
| public static class Node { public int value; public Node next;
public Node(int val) { this.value = val; } }
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].next = null; return nodeArr[0]; }
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 void swap(Node[] nodeArr, int a, int b) { Node tmp = nodeArr[a]; nodeArr[a] = nodeArr[b]; nodeArr[b] = tmp; }
public static Node listPartition2(Node head, int pivot) { Node sH = null; Node sT = null; Node eH = null; Node eT = null; Node mH = null; Node mT = null; Node next = null; 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 (mH == null) { mH = head; mT = head; } else { mT.next = head; mT = head; } } head = next; }
if (sT != null) { sT.next = eH; eT = eT == null ? sT : eT; } if (eT != null) { eT.next = mH; } return sH != null ? sH : (eH != null ? eH : mH); }
|
3.复制带随机指针的链表(LeetCode 138. medium)
链表节点有一个新增的指针,该指针可以指向链表中的任何节点或空节点。
给定一个此类节点组成的无环单链表头节点,要求实现链表的复制,返回新链表头节点。
要求时间复杂度O(N),额外空间复杂度O(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 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
| public static class Node { int val; Node next; Node random;
public Node(int val) { this.val = val; this.next = null; this.random = null; } }
public static Node copyRandomList1(Node head) { Map<Node, Node> map = new HashMap<Node, Node>(); Node cur = head; while (cur != null) { map.put(cur, new Node(cur.val)); cur = cur.next; } cur = head; while (cur != null) { map.get(cur).next = map.get(cur.next); map.get(cur).random = map.get(cur.random); cur = cur.next; } return map.get(head); }
public static Node copyRandomList2(Node head) { if (head == null) { return null; } Node cur = head; Node next = null; while (cur != null) { next = cur.next; cur.next = new Node(cur.val); cur.next.next = next; cur = next; } cur = head; Node copy = null; while (cur != null) { next = cur.next.next; copy = cur.next; copy.random = cur.random != null ? cur.random.next : null; cur = next; } Node res = head.next; cur = head; while (cur != null) { next = cur.next.next; copy = cur.next; cur.next = next; copy.next = next != null ? next.next : null; cur = next; } return res; }
|
4.链表相交(LeetCode 160. 141. 142. ,相似)
给定两个可能有环也可能无环的单链表的头结点head1和head2,请找出两个链表相交的第一个节点,如果不存在返回null。
要求时间复杂度O(N),空间复杂度O(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 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 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138
| public static class Node { public int value; public Node next;
public Node(int value) { this.value = value; } }
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 Node getLoopNode(Node head) { if (head == null || head.next == null || head.next.next == null) { return null; }
Node slow = head.next; Node fast = head.next.next; while (slow != fast) { if (fast.next == null || fast.next.next == null) { return null; } slow = slow.next; fast = fast.next.next; }
fast = head; while (slow != fast) { slow = slow.next; fast = fast.next; } return slow; }
public static Node noLoop(Node head1, Node head2) { if (head1 == null || head2 == null) { return null; }
Node cur1 = head1; Node cur2 = head2; int sum = 0; while (cur1.next != null) { sum++; cur1 = cur1.next; } while (cur2.next != null) { sum--; cur2 = cur2.next; }
if (cur1 != cur2) { return null; }
cur1 = sum > 0 ? head1 : head2; cur2 = cur1 == head1 ? head2 : head1; sum = Math.abs(sum); while (sum != 0) { sum--; cur1 = cur1.next; } while (cur1 != cur2) { cur1 = cur1.next; cur2 = cur2.next; } return cur1; }
public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) { Node cur1 = null; Node cur2 = null; if (loop1 == loop2) { cur1 = head1; cur2 = head2; int n = 0; while (cur1 != loop1) { n++; cur1 = cur1.next; } while (cur2 != loop2) { n--; cur2 = cur2.next; } 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; }
}
|