- sort list
這道題實(shí)在是有點(diǎn)繁瑣矿卑，要求sort一個(gè)LinkedList，并且runtime是O(n lg n）沃饶，space complexity必須是constant母廷。從runtime來篩選的話，可以用merge sort和heap sort糊肤，但是heap sort必須是有index的情況才可以使用琴昆，因?yàn)閔eap sort必須通過index得到left right。因此馆揉，這里只能用mergesort业舍。但是考慮到space complexity的要求，無法使用一般的recursion形式的mergesort升酣，必須是in place舷暮。
看了discussion的答案好久才想明白。
還是用比較經(jīng)典的merge sort思路噩茄，只不過split這一步下面，是根據(jù)長(zhǎng)度截取兩段left和right，與此同時(shí)要記下下一次要開始截取的點(diǎn)绩聘。截取了left right之后將這兩段merge沥割。這里的變化因素就是截取的長(zhǎng)度，長(zhǎng)度每次翻倍凿菩，1机杜，2，4衅谷，椒拗。。会喝。
每次長(zhǎng)度變化都從頭開始陡叠，重復(fù)一邊split和merge的過程玩郊。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
// cannot use heapsort because we cannot get the left and right by index
// so consider about inplace mergesort
// mergesort
if (head == null || head.next == null) {
return head;
}
// get the length of the linked list
int len = 0;
ListNode dummy = new ListNode(0);
dummy.next = head;
while (head != null) {
head = head.next;
len++;
}
// split and merge here
for (int i = 1; i < len; i <<= 1) {
ListNode tail = dummy;
ListNode cur = dummy.next;
while (cur != null) {
ListNode left = cur;
ListNode right = split(left, i);
cur = split(right, i);
tail = merge(left, right, tail);
}
}
return dummy.next;
}
// cut length of step of the LinkedList for head;
// return the begining of this part, set the end of length n linkedlist null
public ListNode split(ListNode head, int step) {
if (head == null) {
return null;
}
while (step > 1 && head.next != null) {
head = head.next;
step--;
}
ListNode res = head.next;
head.next = null;
return res;
}
// merge two split part, and then append to the tail
// return the tail of merged linkedlist
public ListNode merge(ListNode left, ListNode right, ListNode end) {
ListNode tail = end;
while (left != null && right != null) {
if (left.val < right.val) {
tail.next = left;
left = left.next;
} else {
tail.next = right;
right = right.next;
}
tail = tail.next;
}
if (left != null) {
tail.next = left;
}
if (right != null) {
tail.next = right;
}
while (tail.next != null) {
tail = tail.next;
}
return tail;
}
}
Merge Two Sorted Lists
這題太簡(jiǎn)單。枉阵。译红。必須一遍過Merge Intervals
也不難。我寫了兩種解法兴溜，一種解法需要一個(gè)list作為過渡侦厚，另一種不需要。
// need another list
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals.length <2) {
return intervals;
}
Arrays.sort(intervals, (a,b)->(a[0]-b[0]));
List<int[]> res = new ArrayList<>();
int[] prev = intervals[0];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] > prev[1]) {
res.add(prev);
prev = intervals[i];
} else {
prev[1] = Math.max(prev[1], intervals[i][1]);
}
}
res.add(prev);
int[][] arr = new int[res.size()][2];
arr = res.toArray(arr);
return arr;
}
}
// do not need another list
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals.length <= 1) {
return intervals;
}
Arrays.sort(intervals, (a,b)->(a[0]-b[0]));
// two pointers, first point to the arranged
int i = 0;
for (int j = 1; j < intervals.length; j++) {
if (intervals[i][1] < intervals[j][0]) {
i++;
intervals[i] = intervals[j];
} else {
intervals[i][1] = Math.max(intervals[i][1],intervals[j][1]);
}
}
int[][] res = Arrays.copyOfRange(intervals, 0, i + 1);
return res;
}
}
- Insertion Sort List
用insertion sort的方法sort一個(gè)linkedlist拙徽。因?yàn)閘inkedlist沒法往前刨沦，所以從最后開始sort。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode insertionSortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
int len = 0;
while (head != null) {
head = head.next;
len++;
}
for (int i = len-1; i > 0; i--) {
ListNode cur = forward(dummy, i);
sort(cur);
}
return dummy.next;
}
public ListNode forward(ListNode head, int i) {
while(i > 0) {
head = head.next;
i--;
}
return head;
}
public void sort(ListNode cur) {
int val = cur.val;
while (cur.next != null) {
if (val > cur.next.val) {
cur.val = cur.next.val;
cur = cur.next;
} else {
break;
}
}
cur.val = val;
}
}
另一種方法就是還是按照原本的insertion sort的方法膘怕，只不過每次不是往前對(duì)比想诅，而是從頭開始對(duì)比。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode insertionSortList(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode helper = dummy, cur = dummy; // cur.next is the node to be inserted
ListNode pre = dummy; // insert between pre and pre.next;
while (cur != null && cur.next != null) {
int val = cur.next.val;
while (pre.next.val < val) {
pre = pre.next;
}
if (pre != cur) {
ListNode tmp = pre.next; // insert
pre.next = new ListNode(val);
pre.next.next = tmp;
cur.next = cur.next.next;
} else {
cur = cur.next;
}
pre = dummy;
}
return dummy.next;
}
}
