首页 > 代码库 > 算法题解之链表

算法题解之链表

Copy List with Random Pointers

复制带随机指针的链表

思路1:使用哈希表,需要消耗O(N)的额外空间。

技术分享
 1 public class Solution {
 2     /**
 3      * @param head: The head of linked list with a random pointer.
 4      * @return: A new head of a deep copy of the list.
 5      */
 6     public RandomListNode copyRandomList(RandomListNode head) {
 7         // write your code here
 8         
 9         Map<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
10         RandomListNode cur = head;
11         RandomListNode copyDummy = new RandomListNode(0);
12         RandomListNode copyCur = copyDummy;
13         
14         while (cur != null) {
15             copyCur.next = new RandomListNode(cur.label);
16             copyCur = copyCur.next;
17             map.put(cur, copyCur);
18             cur = cur.next;
19         }
20         
21         cur = head;
22         while (cur != null) {
23             copyCur = map.get(cur);
24             copyCur.random = map.get(cur.random);
25             cur = cur.next;
26         }       
27         return copyDummy.next;
28     }
29 }
View Code

思路2:第一遍扫的时候巧妙运用next指针, 开始数组是1->2->3->4 。 然后扫描过程中 先建立copy节点 1->1`->2->2`->3->3`->4->4`, 然后第二遍copy的时候去建立边的copy, 拆分节点, 一边扫描一边拆成两个链表,这里用到两个dummy node。第一个链表变回 1->2->3 , 然后第二变成 1`->2`->3` 。消耗额外空间O(1)。

技术分享
 1 public class Solution {
 2     /**
 3      * @param head: The head of linked list with a random pointer.
 4      * @return: A new head of a deep copy of the list.
 5      */
 6     public RandomListNode copyRandomList(RandomListNode head) {
 7         // write your code here
 8         copyNext(head);
 9         copyRandom(head);
10         return split(head);
11         
12     }
13     
14     public RandomListNode split(RandomListNode head) {
15         RandomListNode dummy = new RandomListNode(0);
16         RandomListNode cur = dummy;
17         
18         while (head != null) {
19             cur.next = head.next;
20             cur = cur.next;
21             head.next = head.next.next;
22             head = head.next;
23         }
24         return dummy.next;
25         
26     }
27     
28     public void copyRandom(RandomListNode head) {
29         
30         while (head != null) {
31             RandomListNode copy = head.next;
32             if (copy.random != null) {
33                 copy.random = copy.random.next;
34             }
35             head = head.next.next;
36         }
37         
38     }
39     
40     public void copyNext(RandomListNode head) {
41       
42         while (head != null) {
43             RandomListNode copy = new RandomListNode(head.label);
44             copy.next = head.next;
45             copy.random = head.random;
46             head.next = copy;
47             head = head.next.next;
48         }
49 
50     }
51 }
View Code

 

 

Convert Binary Search Tree to Doubly Linked List

将二叉查找树转换成双链表

思路:用分治法做,分治函数要返回该子树对应的双链表的头节点和尾节点。

技术分享
 1 /**
 2  * Definition of TreeNode:
 3  * public class TreeNode {
 4  *     public int val;
 5  *     public TreeNode left, right;
 6  *     public TreeNode(int val) {
 7  *         this.val = val;
 8  *         this.left = this.right = null;
 9  *     }
10  * }
11  * Definition for Doubly-ListNode.
12  * public class DoublyListNode {
13  *     int val;
14  *     DoublyListNode next, prev;
15  *     DoublyListNode(int val) {
16  *         this.val = val;
17  *         this.next = this.prev = null;
18  *     }
19  * }
20  */ 
21 public class Solution {
22     /**
23      * @param root: The root of tree
24      * @return: the head of doubly list node
25      */
26     public DoublyListNode bstToDoublyList(TreeNode root) {  
27         // Write your code here
28         return helper(root).head;
29     }
30     
31     public Pair helper(TreeNode root) {
32         if (root == null) {
33             return new Pair(null, null);
34         }
35         Pair leftPair = helper(root.left);
36         Pair rightPair = helper(root.right);
37         DoublyListNode rootNode = new DoublyListNode(root.val);
38         rootNode.next = rightPair.head;
39         rootNode.prev = leftPair.tail;
40         
41         if (leftPair.head == null && rightPair.head == null) {
42             return new Pair(rootNode, rootNode);
43         } else if (leftPair.head == null) {
44             rightPair.head.prev = rootNode;
45             return new Pair(rootNode, rightPair.tail);
46         } else if (rightPair.head == null) {
47             leftPair.tail.next = rootNode;
48             return new Pair(leftPair.head, rootNode);
49         } else {
50             rightPair.head.prev = rootNode;
51             leftPair.tail.next = rootNode;
52             return new Pair(leftPair.head, rightPair.tail);
53         }
54         
55     }
56 }
57 
58 class Pair {
59     DoublyListNode head;
60     DoublyListNode tail;
61     Pair(DoublyListNode head, DoublyListNode tail) {
62         this.head = head;
63         this.tail = tail;
64     }
65 }
View Code

 

 

Convert Sorted List to Balanced BST

排序列表转换为二分查找树

思路:分治法。找到链表中点,中点作为根节点,左半段构造一个BST作为左子树,右半段构造一个BST作为右子树。

技术分享
 1 /**
 2  * Definition for ListNode.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int val) {
 7  *         this.val = val;
 8  *         this.next = null;
 9  *     }
10  * }
11  * Definition of TreeNode:
12  * public class TreeNode {
13  *     public int val;
14  *     public TreeNode left, right;
15  *     public TreeNode(int val) {
16  *         this.val = val;
17  *         this.left = this.right = null;
18  *     }
19  * }
20  */ 
21 public class Solution {
22     /**
23      * @param head: The first node of linked list.
24      * @return: a tree node
25      */
26     public TreeNode sortedListToBST(ListNode head) {  
27         // write your code here
28         if (head == null) {
29             return null; 
30         }
31         
32         if (head.next == null) {
33             return new TreeNode(head.val);
34         }
35         
36         if (head.next.next == null) {
37             TreeNode root = new TreeNode(head.val);
38             root.right = new TreeNode(head.next.val);
39             return root;
40         }
41         
42         ListNode befMid = beforeMid(head);
43         TreeNode root = new TreeNode(befMid.next.val);
44         root.right = sortedListToBST(befMid.next.next);
45         befMid.next = null;
46         root.left = sortedListToBST(head);
47         
48         return root;
49         
50     }
51     
52     public ListNode beforeMid(ListNode head) {
53         ListNode cur = head;
54         int length = 0;
55         while (cur != null) {
56             cur = cur.next;
57             length++;
58         }
59         
60         int mid = (length + 1) / 2;
61         for(int i = 2; i <= mid -1; i++){
62             head = head.next;
63         }
64         
65         return head;
66     }
67 }
View Code

 

 

Linked List Cycle

带环链表

思路:先起一个快指针和一个慢指针,如果快慢指针能相遇,说明带环。

技术分享
 1 /**
 2  * Definition for ListNode.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int val) {
 7  *         this.val = val;
 8  *         this.next = null;
 9  *     }
10  * }
11  */ 
12 public class Solution {
13     /**
14      * @param head: The first node of linked list.
15      * @return: True if it has a cycle, or false
16      */
17     public boolean hasCycle(ListNode head) {  
18         // write your code here
19         if (head == null || head.next == null) {
20             return false;
21         }
22         ListNode slow = head;
23         ListNode fast = head.next;
24         while (fast != null && fast.next != null) {
25             if (slow == fast) {
26                 return true;
27             }
28             slow = slow.next;
29             fast = fast.next.next;
30         }
31         return false;
32     }
33 }
View Code

 

 

Linked List Cycle II

带环链表II

思路:先起一个快指针和一个慢指针,快指针和慢指针重合时,从表头再起一个慢指针,两个慢指针继续走,相遇的地方就是环的入口。

技术分享
 1 /**
 2  * Definition for ListNode.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int val) {
 7  *         this.val = val;
 8  *         this.next = null;
 9  *     }
10  * }
11  */ 
12 public class Solution {
13     /**
14      * @param head: The first node of linked list.
15      * @return: The node where the cycle begins. 
16      *           if there is no cycle, return null
17      */
18     public ListNode detectCycle(ListNode head) {  
19         // write your code here
20         if (head == null || head.next == null) {
21             return null;
22         }
23         ListNode slow = head;
24         ListNode fast = head.next;
25         
26         while (slow != fast) {
27             if (fast == null || fast.next == null) {
28                 return null;
29             }
30             slow = slow.next;
31             fast = fast.next.next;
32         }
33         
34         while (head != slow.next) {
35             head = head.next;
36             slow = slow.next;
37         }
38         return head;
39         
40     }
41 }
View Code

 

 

merge k sorted lists

合并k个排序链表

思路1:分治法。

  时间复杂度分析:

技术分享
 1 T(N,k) = T(N1, k/2) + T(N2, k/2) + N1 + N2
 2 
 3      = T(N1, k/2) + T(N2, k/2) + N
 4 
 5      = T(N11, k/4)  + T(N12, k/4) + N11 + N12 + T(N21, k/4) + T(N22, k/4)   + N21 + N22 + N
 6 
 7      = T(N11, k/4)  + T(N12, k/4) + N1 + T(N21, k/4) + T(N22, k/4) + N2 + N
 8 
 9      = T(N11, k/4)  + T(N12, k/4) + T(N21, k/4) + T(N22, k/4) + 2N
10 
11      ......
12 
13      = T(n1, 1) + T(n2, 1) +...+ T(nk, 1) + Nlgk = O(Nlgk)
14             
View Code
技术分享
 1 public class Solution {
 2     /**
 3      * @param lists: a list of ListNode
 4      * @return: The head of one sorted list.
 5      */
 6     public ListNode mergeKLists(List<ListNode> lists) {
 7         if (lists.size() == 0) {
 8             return null;
 9         }
10         return mergeHelper(lists, 0, lists.size() - 1);
11     }
12     
13     private ListNode mergeHelper(List<ListNode> lists, int start, int end) {
14         if (start == end) {
15             return lists.get(start);
16         }
17         
18         int mid = start + (end - start) / 2;
19         ListNode left = mergeHelper(lists, start, mid);
20         ListNode right = mergeHelper(lists, mid + 1, end);
21         return mergeTwoLists(left, right);
22     }
23     
24     private ListNode mergeTwoLists(ListNode list1, ListNode list2) {
25         ListNode dummy = new ListNode(0);
26         ListNode tail = dummy;
27         while (list1 != null && list2 != null) {
28             if (list1.val < list2.val) {
29                 tail.next = list1;
30                 tail = list1;
31                 list1 = list1.next;
32             } else {
33                 tail.next = list2;
34                 tail = list2;
35                 list2 = list2.next;
36             }
37         }
38         if (list1 != null) {
39             tail.next = list1;
40         } else {
41             tail.next = list2;
42         }
43         
44         return dummy.next;
45     }
46 }
View Code

 思路2:最小堆

时间复杂度分析:T(N, k) = N * lgk = O(Nlgk)

技术分享
 1 public class Solution {
 2     /**
 3      * @param lists: a list of ListNode
 4      * @return: The head of one sorted list.
 5      */
 6     public ListNode mergeKLists(List<ListNode> lists) {  
 7         // write your code here
 8         if (lists == null || lists.size()==0) {
 9             return null;
10         }
11         Comparator<ListNode> listNodeComparator = new Comparator<ListNode>() {
12             public int compare(ListNode l1, ListNode l2) {
13                 if (l1 == null && l2 == null) {
14                     return 1;
15                 } else if (l1 == null) {
16                     return 1;
17                 } else if (l2 == null) {
18                     return -1;
19                 } else {
20                     return l1.val - l2.val;
21                 }
22             }
23         };
24         
25         ListNode dummy = new ListNode(0);
26         ListNode cur = dummy;
27         
28         PriorityQueue<ListNode> minHeap = new PriorityQueue<ListNode>(lists.size(), listNodeComparator);
29         for (ListNode l : lists) {
30             if (l != null) {
31                 minHeap.offer(l);
32             }
33         }
34         
35         while (minHeap.peek() != null) {
36             cur.next = minHeap.poll();
37             cur = cur.next;
38             if (cur.next != null) {
39                 minHeap.offer(cur.next);
40             }
41         }
42         cur.next = null;
43         return dummy.next;  
44     } 
45 }
View Code

 思路3:两两合并。

时间复杂度分析:

技术分享
1 T(N, k) = N + T(N, k/2)
2 
3       = 2N + T(N, k/4)
4 
5       = 3N + T(N, k/8)
6 
7        ......
8 
9       = Nlgk + T(N, 1) = O(Nlgk)
View Code
技术分享
 1 public class Solution {
 2     /**
 3      * @param lists: a list of ListNode
 4      * @return: The head of one sorted list.
 5      */
 6     public ListNode mergeKLists(List<ListNode> lists) {  
 7         // write your code here
 8         if (lists.size() == 0) {
 9             return null;
10         }
11         if (lists.size() == 1) {
12             return lists.get(0);
13         }
14         int size = lists.size();
15         List<ListNode> nextLists = new ArrayList<ListNode>();
16         for (int i = 0; i<=size-1; i+=2) {
17             if (i == size-1) {
18                 nextLists.add(lists.get(i));
19                 break;
20             }
21             ListNode afterMerge = mergeTwoLists(lists.get(i), lists.get(i+1));
22             nextLists.add(afterMerge);
23         }
24         return mergeKLists(nextLists);
25     }
26     
27     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
28         ListNode dummy = new ListNode(0);
29         ListNode cur = dummy;
30         
31         while (l1 != null && l2 != null) {
32             if (l1.val <= l2.val) {
33                 cur.next = l1;
34                 cur = cur.next;
35                 l1 = l1.next;
36             } else {
37                 cur.next = l2;
38                 cur = cur.next;
39                 l2 = l2.next;
40             }
41         }
42         
43         if (l1 != null) {
44             cur.next = l1;
45         }
46         
47         if (l2 != null) {
48             cur.next = l2;
49         }
50         
51         return dummy.next;
52     }
53 }
View Code

 

 

Partition List 

链表划分

思路:用两个dummy接,最后再把两段合起来。

技术分享
 1 /**
 2  * Definition for ListNode.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int val) {
 7  *         this.val = val;
 8  *         this.next = null;
 9  *     }
10  * }
11  */ 
12 public class Solution {
13     /**
14      * @param head: The first node of linked list.
15      * @param x: an integer
16      * @return: a ListNode 
17      */
18     public ListNode partition(ListNode head, int x) {
19         // write your code here
20         ListNode leftDummy = new ListNode(0);
21         ListNode rightDummy = new ListNode(0);
22         ListNode left = leftDummy;
23         ListNode right = rightDummy;
24         ListNode cur = head;
25         
26         while (cur != null) {
27             if (cur.val >= x) {
28                 right.next = cur;
29                 right = cur;
30             } else {
31                 left.next = cur;
32                 left = cur;
33             }
34             cur = cur.next;
35         }
36         
37         right.next = null;
38         left.next = rightDummy.next;
39         return leftDummy.next;
40     }
41 }
View Code

 

 

Palindrome Linked List

回文链表

思路:从链表中间切开,对第二段链表做反转,然后看两段链表是否一 一对应。

技术分享
 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) { val = x; }
 7  * }
 8  */
 9 public class Solution {
10     /**
11      * @param head a ListNode
12      * @return a boolean
13      */
14     public boolean isPalindrome(ListNode head) {
15         // Write your code here
16         if (head == null || head.next == null) {
17             return true;
18         }
19         ListNode mid = findMid(head);
20         ListNode aftermid = reverse(mid.next);
21         while (aftermid != null) {
22             if (aftermid.val != head.val) {
23                 return false;
24             }
25             aftermid = aftermid.next;
26             head = head.next;
27         }
28         return true;
29         
30     }
31     
32     public ListNode findMid(ListNode head) {
33         if (head == null || head.next == null) {
34             return head;
35         }
36         ListNode slow = head;
37         ListNode fast = head.next;
38         while (fast != null && fast.next != null) {
39             slow = slow.next;
40             fast = fast.next.next;
41         }
42         return slow;
43     }
44     
45     public ListNode reverse(ListNode head) {
46         if (head == null || head.next == null) {
47             return head;
48         }
49         ListNode pre = head;
50         ListNode cur = head.next;
51         while (cur != null) {
52             ListNode tmp = cur;
53             cur = cur.next;
54             tmp.next = pre;
55             pre = tmp;
56         }
57         head.next = null;
58         return pre;
59     }
60 }
View Code

 

 

Reverse Nodes in k-Group

k组翻转链表

思路:先判断能否翻转,如果能,先翻转第一段,后面的递归地进行翻转。

技术分享
 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) { val = x; }
 7  * }
 8  */
 9 public class Solution {
10     /**
11      * @param head a ListNode
12      * @param k an integer
13      * @return a ListNode
14      */
15     public ListNode reverseKGroup(ListNode head, int k) {
16         if (head == null || head.next == null) {
17             return head;
18         }
19         
20         ListNode cur = head;
21         int count = 0;
22         while (cur != null && count < k) {
23             cur = cur.next;
24             count++;
25         }
26         if (count < k) {
27             return head;
28         }
29         ListNode pre = head;
30         cur = head.next;
31         count = 1;
32         while (count < k) {
33             ListNode tmp = cur;
34             cur = cur.next;
35             tmp.next = pre;
36             pre = tmp;
37             count++;
38         }
39         head.next = reverseKGroup(cur, k);
40         return pre;
41     }
42 }
View Code

 

 

Swap Two Nodes in Linked List

交换链表中两个节点

思路:先查找这两个节点,如果存在就有两种情况:两个节点相邻,两个节点不相邻。要分开讨论。

技术分享
 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) { val = x; }
 7  * }
 8  */
 9 public class Solution {
10     /**
11      * @param head a ListNode
12      * @oaram v1 an integer
13      * @param v2 an integer
14      * @return a new head of singly-linked list
15      */
16     public ListNode swapNodes(ListNode head, int v1, int v2) {
17         // Write your code here
18         ListNode dummy = new ListNode(0);
19         dummy.next = head;
20         ListNode pre1 = null;
21         ListNode pre2 = null;
22         ListNode cur = dummy;
23         while (cur.next != null) {
24             if (cur.next.val == v1) {
25                 pre1 = cur;
26             } 
27             if (cur.next.val == v2) {
28                 pre2 = cur;
29             } 
30             cur = cur.next;
31         }
32         
33         if (pre1 == null || pre2 == null) {
34             return dummy.next;
35         }
36         if (pre1.val == v2) {
37             ListNode tmp = pre1.next;
38             pre2.next = tmp;
39             pre1.next = tmp.next;
40             tmp.next = pre1;
41         } else if (pre2.val == v1) {
42             ListNode tmp = pre2.next;
43             pre1.next = tmp;
44             pre2.next = tmp.next;
45             tmp.next = pre2;
46         } else {
47             ListNode n1 = pre1.next;
48             ListNode n2 = pre2.next;
49             pre1.next = n2;
50             pre2.next = n1;
51             ListNode tmp = n1.next;
52             n1.next = n2.next;
53             n2.next = tmp;
54         }
55         
56         return dummy.next;
57     }
58 }
View Code

 

 

 Sort List

链表排序

思路1:快速排序。

技术分享
 1 /**
 2  * Definition for ListNode.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int val) {
 7  *         this.val = val;
 8  *         this.next = null;
 9  *     }
10  * }
11  */ 
12 public class Solution {
13     /**
14      * @param head: The head of linked list.
15      * @return: You should return the head of the sorted linked list,
16                     using constant space complexity.
17      */
18     public ListNode sortList(ListNode head) {  
19         // write your code here
20         if (head == null || head.next == null) {
21             return head;
22         }
23         resultType pair = partition(head, head.val);
24         ListNode left = sortList(pair.l1);
25         ListNode right = sortList(pair.l2);
26         ListNode equal = pair.l3;
27         
28         ListNode dummy = new ListNode(0);
29         dummy.next = left;
30         ListNode leftTail = dummy;
31         
32         
33         while (leftTail.next != null) {
34             leftTail = leftTail.next;
35         }
36         
37         if (equal != null) {
38             leftTail.next = equal;
39             while (equal.next != null) {
40                 equal = equal.next;
41             }
42 
43             equal.next = right;
44         } else {
45             leftTail.next = right;
46         }
47         return dummy.next;
48     }
49     
50     public resultType partition(ListNode head, int x) {
51         ListNode leftDummy = new ListNode(0);
52         ListNode rightDummy = new ListNode(0);
53         ListNode equalDummy = new ListNode(0);
54         ListNode leftTail = leftDummy;
55         ListNode rightTail = rightDummy;
56         ListNode equalTail = equalDummy;
57         
58         while (head != null) {
59             if (head.val < x) {
60                 leftTail.next = head;
61                 head = head.next;
62                 leftTail = leftTail.next;
63             } else if (head.val > x) {
64                 rightTail.next = head;
65                 head = head.next;
66                 rightTail = rightTail.next;
67             } else {
68                 equalTail.next = head;
69                 head = head.next;
70                 equalTail = equalTail.next;
71             }
72         }
73         leftTail.next = null;
74         rightTail.next = null;
75         equalTail.next = null;
76         
77         return new resultType(leftDummy.next, rightDummy.next, equalDummy.next);
78         
79     }
80     
81 }
82 
83 class resultType {
84     ListNode l1;
85     ListNode l2;
86     ListNode l3;
87     resultType(ListNode l1, ListNode l2, ListNode l3) {
88         this.l1 = l1;
89         this.l2 = l2;
90         this.l3 = l3;
91     }
92 }
View Code

思路2:归并排序也是可以的,因为链表的merge操作不需要额外的空间。

算法题解之链表