LinkedList
2017-10-14 本文已影响0人
函仔
Merge Two Sorted Lists
1.corner case要注意：当两个list都是空的时候，返回空
2.连接node的条件是用while，出口是两个有一个空了
3.感觉Linkedlist的尿性就是while到空/到不空
4.最后连接链表的时候是用 if (不空)，而非while(不空)，因为链表和数组不一样，链表已经连好了，数组肯定是用while(不空)
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null && l2 == null) {
return null;
}
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
if (l1 != null) {
tail.next = l1;
}
if (l2 != null) {
tail.next = l2;
}
return dummy.next;
}
Sort List
一共有三个版本
一、MergeSort
1.这个版本用到了①找LinkedList中点的迷你程序 以及②上面的Merge 2 sorted list
2.corner case 是head 为空或者head只有一个
3.LinkedList的mergeSort和数组中的mergeSort很像啊
4.注意找到终点后，前面半截要把尾巴null掉，很重要，然后就递归排下去并merge啦
5.MergeSort只用到了left和right. 本质上就是左右两条链；QuickSort用到了left, mid, right，对于每个head，和mid比，小于的链到左边，等于的链到中间，大于的链到右边
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode middle = findMid(head);
ListNode right = sortList(middle.next);
middle.next = null;
ListNode left = sortList(head);
return merge(left, right);
}
//找LinkedList中点的迷你程序
private ListNode findMid(ListNode head) {
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
private ListNode merge(ListNode head1, ListNode head2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
//为什么是while,下面这一行最难想
while (head1 != null && head2 != null) {
if (head1.val < head2.val) {
tail.next = head1;
head1 = head1.next;
} else {
tail.next = head2;
head2 = head2.next;
}
tail = tail.next;
}
//这里同样要注意不是while而是if
if (head1 != null) {
tail.next = head1;
}
if (head2 != null) {
tail.next = head2;
}
return dummy.next;
}
}
二、QuickSort1
这个方法我觉得和数组的qs还是有一丢丢区别，数组的是两边交换，LinkedList方法是先找到mid, 然后分成了左中右三个list，再从头看小于mid放左边，等于mid放中间，大于mid放右边。哎本质上还是一样的啦
做链接的时候要用dummy
getNode的时候不用dummy需要控制出口（need to work on that
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 又要做链接了，于是dummyNode又出现了
ListNode leftDummy = new ListNode(0);
ListNode leftTail = leftDummy;
ListNode middleDummy = new ListNode(0);
ListNode middleTail = middleDummy;
ListNode rightDummy = new ListNode(0);
ListNode rightTail = rightDummy;
ListNode mid = findMid(head);
while (head != null) {
if (head.val < mid.val) {
leftTail.next = head;
leftTail = leftTail.next;
} else if (head.val > mid.val) {
rightTail.next = head;
rightTail = rightTail.next;
} else {
middleTail.next = head;
middleTail = middleTail.next;
}
head = head.next;
}
//一轮过后，把链切掉,不切掉会有bug，因为之前leftTail.next = head
//head后面有一堆呢
leftTail.next = null;
middleTail.next = null;
rightTail.next = null;
//连接之前要保证左右两边都是排好序的
ListNode left = sortList(leftDummy.next);
ListNode right = sortList(rightDummy.next);
return concat(left, middleDummy.next, right);
}
//plz熟练背出
private ListNode findMid(ListNode head) {
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
System.out.println(slow.val);
return slow;
}
//做链接的时候总是要dummynode
private ListNode concat(ListNode left, ListNode middle, ListNode right) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
tail.next = left;
tail = getTail(tail);
tail.next = middle;
tail = getTail(tail);
tail.next = right；
return dummy.next;
}
//get的时候就不需要dummy,但是要总结出口
private ListNode getTail(ListNode head) {
//纯corner case 并不是什么递归退出的条件
//and这非常重要，很有可能链是空的
if (head == null) {
return null;
}
//从这里退出说明head.next == null,即head是最后一个了
while (head.next != null) {
head = head.next;
}
return head;
}
}
QuickSort2
这个方法还没看
Linked List Cycle
又是一个快慢指针，这道题就是知道结果纯考coding
空指针来源于取null.next
public boolean hasCycle(ListNode head) {
public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
ListNode fast = head;
ListNode slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
return true;
}
}
return false;
}
Linked List Cycle 2
找环的入口，当快慢指针重合时，head和slow分别往下移，移到两个指针重叠 ，叮！We find it!!
public ListNode detectCycle(ListNode head) {
if (head == null) {
return null;
}
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
if (slow == fast) {
ListNode point = head;
while (point != slow) {
point = point.next;
slow = slow.next;
}
return slow;
}
}
return null;
}
160.Intersection of Two Linked Lists
Linked List Cycle 2的变种题
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
由a1找到c3, 将c3连到b1,就成了Linked List Cycle2找环入口
找到之后记得将c3-->null 恢复原链
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
//别直接操作headA,赋值给一个新的node再操作,本题headA后面又用到了
ListNode node = headA;
while (node.next != null) {
node = node.next;
}
node.next = headB;
ListNode result = LinkedListCycleII(headA);
node.next = null;
return result;
}
private ListNode LinkedListCycleII(ListNode head) {
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
if (slow == fast) {
ListNode point = head;
while (point != slow) {
slow = slow.next;
point = point.next;
}
return slow;
}
}
return null;
}
}
138.Copy List with Random Pointer
首先，这是一道恶心的题，一定要画图
copyNext(head);
copyRandom(head);
splitList(head);
这三个都需要扫head，所以有while(head != null)
/**
* Definition for singly-linked list with a random pointer.
* class RandomListNode {
* int label;
* RandomListNode next, random;
* RandomListNode(int x) { this.label = x; }
* };
*/
public class Solution {
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null) {
return null;
}
//对没错，链表结构是改了，但是head并没有变成tail啊
//Java是pass by value, 传到函数里是head的地址
//然而呢操作了半天head的地址并没有变
copyNext(head);
copyRandom(head);
return splitList(head);
}
//需要画图！！！
private void copyNext(RandomListNode head) {
while (head != null) {
RandomListNode newNode = new RandomListNode(head.label);
//这里就不拷贝random了
//newNode.random = head.random;不要这个
//果然我掌握了机理 我好厉害
newNode.next = head.next;
head.next = newNode;
head = head.next.next;
}
}
private void copyRandom(RandomListNode head) {
while (head != null) {
if (head.random != null) {
head.next.random = head.random.next;
}
//因为head后面总是跟着一个一样的，所以不存在head.next就为null的问题
head = head.next.next;
}
}
split的时候和random没关系，split的是next的部分
private RandomListNode splitList(RandomListNode head) {
//不存在head只为1个的问题，因为之前head一定是copy过了的，至少俩
//初始设定 这是一定要有的 要返回的 设了就无须再动了
RandomListNode newHead = head.next;
while (head != null) {
//temp很关键，既连老链，又连新链
RandomListNode temp = head.next;
//连接老链
head.next = temp.next;
head = head.next;
//连接新链，temp.next != null也就确保了temp.next.next不是空
//因为temp.next的值等于temp.next.next
//而且temp是比head要超前的所以要单独判断一下是否next为null
if (temp.next != null) {
temp.next = temp.next.next;
}
}
return newHead;
}
}
- Palindrome Linked List
奇数个节点：1--->2--->3--->2--->1
把右边的链定在: 2--->1
偶数个节点：1--->2--->3--->3--->2--->1
把右边的链定在: 3--->2--->1
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null) {
return true;
}
ListNode fast = head;
ListNode slow = head;
//当使用这种方法找中间位时，已经要记得在前面检查 head==null
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//然后无论如何记住本题的右边的链是短的那个
//奇数个节点：1--->2--->3--->2--->1(因为出上述循环时fast指向1，并非null哦，于是slow就又挪了一格
//把右边的链定在: 2--->1
//偶数个节点：1--->2--->3--->3--->2--->1--->NULL(fast到2就停下了，并非null
//于是slow也要挪一格
//把右边的链定在: 3--->2--->1
if (fast != null) {
slow = slow.next;
}
//这个千万要赋值给slow,否则slow就不是指向最后一位了，而是仍指向中间位
slow = reverse(slow);
fast = head;
while (slow != null) {
if (fast.val != slow.val) {
return false;
}
fast = fast.next;
slow = slow.next;
}
return true;
}
//请无脑写出 谢谢！
private ListNode reverse(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
}
