Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.
这一题我给你们盗张图你们就看懂了。
根据上一题的思路，如果链表有环，fast与slow最终会在z相遇。那么fast走过的路为a+b+c+b， 而slow走过的路是a+b。
那么fast每次走两步，slow每次走一步。相遇时fast走过的节点数是slow的二倍，这一点很容易理解。所以得到下面等式：
a+b+c+b = 2(a+b)
a = c
也就是说，从Z点到Y点的节点数与从X(head)点到Y点的节点数。而这个Y点就是我们要找的链表起始处。那么现在思路清晰了吧，如果检测到有环，那么就让fast慢下来，一次走一步，而另外找一个指针从头走，每次也只走一步。那么这两个指针相遇点的位置就是链表的起始处。
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { if (null == head || null == head.next){ return null; } ListNode fast = head, slow = head; do { if (fast != null){ fast = fast.next; } else { break; } if (fast != null){ fast = fast.next; } else { break; } slow = slow.next; }while (fast != slow); if (null == fast){ return null; } ListNode ans = head; while (ans != slow){ ans = ans.next; slow = slow.next; } return ans; } }
Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes' values.
这个问题比较简单，分三部做就好了。 一：将链表平分，由两个指针均指向表头，一个指针(slow)每次移动一步，另外一个(fast)每次移动两步。当fast走到头的时候，slow指向的就是链表的中央。 二：将分后的后半部分链表逆序，送分题。 三：将两个部分按序依次组成新链表。 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public void reorderList(ListNode head) { if (null == head || null == head.next){ return; } ListNode reverse = reverseList(divide(head)); ListNode current = head, tmp = head; current = current.next; while (current != null && reverse != null){ tmp.next = reverse; reverse = reverse.next; tmp = tmp.next; tmp.next = current; current = current.next; tmp = tmp.next; } tmp.next = current != null ? current : reverse; } private ListNode divide(ListNode head){ if (null == head || null == head.next){ return head; } ListNode fast = head.next, slow = head; while (fast != null){ fast = fast.next; if (fast != null){ fast = fast.next; } else { break; } slow = slow.next; } ListNode middle = slow.next; slow.next = null; return middle; } private ListNode reverseList(ListNode head){ if (null == head || null == head.next){ return head; } ListNode currentHead = head.next, tmp = null; head.next = null; while (currentHead != null){ tmp = currentHead; currentHead = currentHead.next; tmp.next = head; head = tmp; } return head; } } 138. Copy List with Random PointerA 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.
这一题，如果只需要copy一个简单的链表，这很简单。麻烦的就是另外一个随机指针，因为如果你直接copy过去的话，生产的链表副本中那个随机的指针指向是原链表中的结点。所以，在这里简单的找一个对应好了。那么一一映射，需要的数据结构就是map。想通这一点，剩下的就是送分题。 /** * Definition for singly-linked list with a random pointer. * class RandomListNode { * int label; * RandomListNode next, random; * RandomListNode(int x) { this.label = x; } * }; */ import java.util.HashMap; public class Solution { public RandomListNode copyRandomList(RandomListNode head) { if (null == head){ return null; } RandomListNode copyHead = new RandomListNode(head.label); HashMap<RandomListNode, RandomListNode> map = new HashMap<>(); RandomListNode original = head, copy = copyHead; while (original!= null){ map.put(original, copy); original = original.next; if (original != null) { copy.next = new RandomListNode(original.label); copy = copy.next; } } original = head; copy = copyHead; while (original != null){ copy.random = map.get(original.random); original = original.next; copy = copy.next; } return copyHead; } } 61. Rotate List Given a list, rotate the list to the right by k places, where k is non-negative. 这一题简单了，先找到链表的总长度length，然后k对length取一下模，是0直接返回，不是0则用旧尾指向旧头，找到length - k 位置处的node，以其下一个节点为新头，并将该节点的next置为null。 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode rotateRight(ListNode head, int k) { if (0 == k || null == head || null == head.next){ return head; } int listLength = 1; ListNode tail = head; while (tail.next != null){ tail = tail.next; listLength++; } k %= listLength; if (0 == k){ return head; } int deplacement = listLength - k - 1; ListNode current = head; while (deplacement-- != 0){ current = current.next; } ListNode ans = current.next; current.next = null; tail.next = head; return ans; } } 19. Remove Nth Node From End of List Given a linked list, remove the n th node from the end of list and return its head. 本来思想很简单，跟上一题基本一致，惭愧啊，被我写复杂了，居然还用了Stack，罪过罪过。就当是见证我自己的进步好了/(ㄒoㄒ)/~~ import java.util.Stack; /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { Stack<ListNode> nodeStack = new Stack<ListNode>(); ListNode current = head; while (current != null) { nodeStack.push(current); current = current.next; } if (n != nodeStack.size()) { current = nodeStack.elementAt(nodeStack.size()-n-1); current.next = current.next.next; } else { head = head.next; } return head; } } 83. Remove Duplicates from Sorted ListGiven a sorted linked list, delete all duplicates such that each element appear only once.
For example, Given 1->1->2, return 1->2. Given 1->1->2->3->3, return 1->2->3.
送分题，下一个不是null且值与当前节点值相同直接删去。 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode deleteDuplicates(ListNode head) { ListNode current = null, tmp = null; if(head == null || head.next == null){ return head; } current = head; tmp = current.next; while (tmp != null) { if(tmp.val != current.val){ current.next = tmp; current = tmp; } tmp = tmp.next; } current.next = tmp; return head; } } 82. Remove Duplicates from Sorted List IIGiven a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example, Given 1->2->3->3->4->4->5, return 1->2->5. Given 1->1->1->2->3, return 2->3.
这一题里面head就是一个比较特殊的节点了，那就引入一个伪头去特殊化。上一题往下看一个节点，这一题看两个，也是很简单的~
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode deleteDuplicates(ListNode head) { if (null == head || null == head.next){ return head; } ListNode falseHead = new ListNode(0); falseHead.next = head; ListNode current = falseHead.next, prev = falseHead; while (current != null){ int length = 1; while (current.next != null && current.val == current.next.val){ current = current.next; length++; } if (length != 1){ prev.next = current.next; } else { prev = current; } current = current.next; } return falseHead.next; } } 86. Partition List
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example, Given 1->4->3->2->5->2 and x = 3, return 1->2->2->4->3->5.
这一题我的想法比较蠢，不知道有啥更好的办法没，读者有的话请跟我讲一下，万分感谢！我就是想直接遍历链表，然后按要求生成两个新链表，最后合在一起。/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode partition(ListNode head, int x) { if (null == head || null == head.next){ return head; } ListNode small = new ListNode(0), larger = new ListNode(0); ListNode smallIndex = small, largerIndex = larger; while (head != null){ if (head.val < x){ smallIndex.next = head; smallIndex = smallIndex.next; } else { largerIndex.next = head; largerIndex = largerIndex.next; } head = head.next; } smallIndex.next = larger.next; largerIndex.next = null; // 没这一句可能会死循环的 return small.next; } } 24. Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head.
For example, Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
不知道说啥，直接上代码吧，这就是链表交换的细节问题，想好需要保留哪几个指针就行。/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode swapPairs(ListNode head) { if (null == head || null == head.next){ return head; } ListNode falseHead = new ListNode(0); falseHead.next = head; ListNode tmp = null, current = falseHead; while (true){ if (current.next != null){ tmp = current.next; if (tmp.next != null){ current.next = tmp.next; } else { break; } tmp.next = current.next.next; current.next.next = tmp; current = tmp; } else { break; } } return falseHead.next; } }
21. Merge Two Sorted Lists
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
这一题做的比较早了，其实也是可以用伪头的方式去特殊化的，但又不想重写了，贴出来引以为戒好了。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1 == null){ return l2; } else if (l2 == null) { return l1; } ListNode root = null, current_tail = null; if (l1.val < l2.val) { root = l1; l1 = l1.next; } else { root = l2; l2 = l2.next; } current_tail = root; while (l1 != null && l2 != null) { if (l1.val < l2.val) { current_tail.next = l1; l1 = l1.next; } else { current_tail.next = l2; l2 = l2.next; } current_tail = current_tail.next; } if (l1 == null) { current_tail.next = l2; } else { current_tail.next = l1; } return root; } } 23. Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
上一题的加强版，这会有k个链表了，不得不用伪头来去特殊化了。这一题我的想法是直接用最小化堆来做，设最终链表的长度为n。需要维护的最小化堆的大小是k，每次对堆操作的开销是logk，需要操作n次。那么最终的时间复杂度是O(n log k)。PS：但愿没有分析错Orz...
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode mergeKLists(ListNode[] lists) { if (null == lists || 0 == lists.length){ return null; } PriorityQueue<ListNode> pq = new PriorityQueue<>(new compare()); for (ListNode l : lists) { if (l != null) { pq.add(l); } } ListNode falseHead = new ListNode(0), tail = falseHead; falseHead.next = null; while (!pq.isEmpty()){ tail.next = pq.poll(); tail = tail.next; if (tail.next != null){ pq.add(tail.next); } } return falseHead.next; } public class compare implements Comparator<ListNode>{ public int compare(ListNode l1, ListNode l2){ return l1.val - l2.val; } } } 25. Reverse Nodes in k-Group
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example, Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
看着怪吓人，居然还是个hard难度的，但思想很简单，先分组，再逆序，记得合起来就行了。/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode reverseKGroup(ListNode head, int k) { if (null == head || null == head.next || k < 2){ return head; } ListNode falseHead = new ListNode(0), tail = falseHead; falseHead.next = head; int i = 0; while (true){ ListNode point = tail; for (i = 0; i < k && point.next != null; i++, point = point.next); if (i != k){ break; } ListNode newHead = point.next; point.next = null; reverseList(tail.next); tail.next.next = newHead; ListNode tmpTail = tail.next; tail.next = point; tail = tmpTail; } return falseHead.next; } private ListNode reverseList(ListNode head){ if (null == head || null == head.next){ return head; } ListNode currentHead = head.next, tmp = null; head.next = null; while (currentHead != null){ tmp = currentHead; currentHead = currentHead.next; tmp.next = head; head = tmp; } return head; } } 92. Reverse Linked List II
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example: Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note: Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.
好了，我做到的该系列的最后一题啦，快写完了，开心o(*￣▽￣*)ブ，以后再遇到再加上。
这一题就顺序找，找到需要逆序的地方开始逆序，逆序到一定的长度停止逆序，将逆序的接在原链表上，剩下的事就是直接返回就好。
为了防止m==1这种特殊情况，伪头的引入毫无违和感。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { if (m == n){ return head; } ListNode falseHead = new ListNode(0); falseHead.next = head; ListNode begin = falseHead; for (int i = 0; i < m-1 && begin != null; i++, begin = begin.next); ListNode current = begin.next.next, newHead = begin.next, tmp = null; for (int i = m; i < n && current != null; i++) { tmp = current.next; current.next = newHead; newHead = current; current = tmp; } begin.next.next = tmp; begin.next = newHead; return falseHead.next; } }
