Archive for November 3rd, 2013
[leetcode] Reorder List | 单链表前后交叉
Posted by: lexigrey on: November 3, 2013
a->b->c->d->e => a->e->b->d->c，要求inplace，不能用额外空间（要不然直接reverse成另一个就好办了），不能直接改动list的值。
这题有点写长了，过一阵看看网上有没有好点的做法。O(n)。
算法：
- 过一遍算出总长度len
- 再过一遍找到中点或第二部分的第一个点(a->b->c->d->e和a->b->c->d的都是c）
- reverse后半部分，变成a->b->c<-d<-e 或者 a->b->c<-d，最后中点c的next置空
- 两头穿插合并，直到找到c这点。c肯定是一起找到（奇数）或者右半部分先找到（偶数）
public void reorderList(ListNode head) {
if (head == null)
return;
ListNode p = head;
int len = 0;
while (p != null) {
len++;
p = p.next;
}
p = head;
for (int k = 0; k < len / 2; k++) {
p = p.next;
} //p points to mid point
ListNode curr = p.next, next;
p.next = null;
while (curr != null) { //开始reverse后半部分
next = curr.next;
curr.next = p;
p = curr;
curr = next;
}//now p points to the last ele
ListNode h = head;
while (h.next != p && h != p) {
ListNode tempH = h.next;
ListNode tempP = p.next;
h.next = p;
p.next = tempH;
h = tempH;
p = tempP;
}
}
Tags: list
[leetcode] Remove Elements + Remove Duplicates from Sorted Array & + Remove Duplicates from Sorted List 1 & 2
Posted by: lexigrey on: November 3, 2013
- In: leetcode
- 4 Comments
几道典型two pointers一快一慢题。记住j要匀速的走，i指向最终想要的数组的最后一个元素（或者倒数第二个，或者第一个可以被change的。。因题而异）。做的挺焦躁的，记下来对比练习：
1. Remove Elements：一个数组，删掉所有出现的x，返回新长度。
- 两个pointer，一个正常走，一个指向真正去掉x的数组的长度。
-
public int removeElement(int[] A, int elem) { int i = 0; for (int j = 0; j < A.length; j++) { if (A[j] != elem) { //should be used A[i] = A[j]; i++; } } return i; }
2. 一个排好序的数组，删掉所有重复，让新数组每个数字只出现一次，返回新数组长度。不许用额外空间。
- i指向最后一个保证valid的元素
- j指向当前exam的元素，所以从1开始；当A[j] == A[i]的时候，说明A[j]是个invalid的，所以接着走
- 可以看出来j肯定走的比i快，所以不用担心i的出界问题
-
public int removeDuplicates(int[] A) { if (A.length == 0) return 0; int i = 0; //right most valid element for (int j = 1; j < A.length; j++) { if (A[j] != A[i]) { //when not equals to right most valid, means this is also valid, extend the valid array i++; A[i] = A[j]; } } return i + 1; }
3.每个数字最多出现两次，比如1, 1, 1, 2, 2, 3 => 1, 1, 2, 2, 3
- 同样，是当前exam的元素和valid array的最后一个（其实这里是倒数第二个）元素比较，而不是A[j]和A[j – 1]比较。后者就要混乱很多。
-
public int removeDuplicates(int[] A) { if (A.length < 2) return A.length; int i = 1; for (int j = 2; j < A.length; j++) { if (A[j] == A[i - 1]) { continue; } else { i++; A[i] = A[j]; } } return i + 1; }
4. 单链表，删除所有出现过两次或以上的元素，比如1->1->2->2->2 => null
- 同样，i指向最后一个valid元素，j是当前exam的
- 但是当A[i] == A[j]的时候，i要缩短，所以要keep一个prev pointer
- j一定要每次都往后走，保证匀速，千万别i动了j却没动。就挂在这了。
-
public ListNode deleteDuplicates(ListNode head) { if (head == null) return null; ListNode dummy = new ListNode(0); dummy.next = head; ListNode prev = dummy, i = head, j = head.next; while (j != null) { if (i.val == j.val) { while (j != null && i.val == j.val) { i.next = j.next; //remove j j = j.next; } prev.next = i.next; //remove i i = prev.next; j = i == null ? null : i.next; } else { j = j.next; i = i.next; prev = prev.next; } } return dummy.next; }
