25. Reverse Nodes in k-Group
这道题有点小复杂。
先求出list的长度。再在while-loop中套一个for-loop，for-loop中将k个node进行reverse，然后再移动到下组
public class Solution {
public ListNode reverseKGroup(ListNode head, int k) { ListNode prevNode = new ListNode(0); prevNode.next = head; ListNode curr = prevNode; // get the list length int i = count(head); while (i >= k) { // reverse k node in the list for (int j = 0; j < k - 1; j++) { ListNode nextNode = curr.next; curr.next = head.next; head.next = curr.next.next; curr.next.next = nextNode; } curr = head; head = head.next; i -= k; } return prevNode.next; } private int count(ListNode head) { ListNode curr = head; int i= 0; while (curr != null) { i++; curr = curr.next; } return i; }}
61. Rotate List
这道题先获得尾部node，再将尾部node的next连上head形成一个环。k可能大于list长度n，所以获得断开点的位置是n - k % n,断开后再返回指针即可。
public class Solution { public ListNode rotateRight(ListNode head, int k) { if (head == null) { return head; } ListNode tail = head; int length = count(head); // get the tail of List while (tail.next != null) { tail = tail.next; } // generate the circle tail.next = head; ListNode breakNode = tail; for (int i = 0; i < (length - k % length); i++) { breakNode = breakNode.next; } ListNode output = breakNode.next; // break the circle breakNode.next = null; return output; } private int count(ListNode head) { ListNode curr = head; int i= 0; while (curr != null) { i++; curr = curr.next; } return i; } }
86. Partition List
将list按X分成两段,小的的一段大的一段，再连起来。。。
public class Solution { public ListNode partition(ListNode head, int x) { ListNode big = new ListNode(0); ListNode bigCurr = big; ListNode small = new ListNode(0); ListNode smallCurr = small; //遍历 while(head != null){ if(head.val < x){//<x成一组 smallCurr.next = head; smallCurr = smallCurr.next; } else {//>=x成一组 bigCurr.next = head; bigCurr = bigCurr.next; } head = head.next; } smallCurr.next = big.next; bigCurr.next = null;//斩断后面的连接 return small.next; } }
148. Sort List
重复使用merge two sorted list方法，将list不断分成两部分，分别进行排序。mergesort思想。。。
public class Solution { public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode fast = head; ListNode slow = head; while (fast.next != null) { fast = fast.next.next; if (fast == null) { break; } slow = slow.next; } // slow node current in center ListNode right = slow.next; slow.next = null; ListNode left = sortList(head); right = sortList(right); return mergeTwoLists(left, right); } public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode lastNode = dummy; while (l1 != null && l2 != null) { if (l1.val < l2.val) { lastNode.next = l1; l1 = l1.next; } else { lastNode.next = l2; l2 = l2.next; } lastNode = lastNode.next; } if (l1 != null) { lastNode.next = l1; } else { lastNode.next = l2; } return dummy.next; } }
