算法小结--LinkedList Recursive/Iterative解法

LinkedList
list.get(index)//O(N)
list.size()//O(1)
 
➤ Dummy Node
巧用一个dummy node的next 来locate一个关键的。比如说，
- tree track the start of the level above current level
 » 117. Populating Next Right Pointers in Each Node II F家微软
http://rainykat.blogspot.com/2017/02/leetcode-33-search-in-rotated-sorted.html


➤ Two Pointer
两个pointer
* 1.slow，slow = slow.next正常loop + 2.fast , fast = fast.next.next 每次走快一步

Ex: find Middle
while(fast != end && fast.next != end){ ...;} slow is middle
» 109. Convert Sorted List to Binary Search Tree(dfs) Zenefit
http://rainykat.blogspot.com/2017/01/leetcodeairbnb-108-convert-sorted-array.html 
» 143. Reorder List
http://rainykat.blogspot.com/2017/03/leetcode-143-reorder-listlinkedlist.html

Ex：查cycle
» 234. Palindrome Linked List F家A家
-- fast/slow ptr to find the half of the list（也用于 148.merge sort，在下面 ）
http://rainykat.blogspot.com/2017/01/leetcodefa-234-palindrome-linked.html

* 1.正常loop， 2 focus关键位置
» 147. Insertion Sort List 各大家
http://rainykat.blogspot.com/2017/03/leetcode-147-insertion-sort-list.html

*2 pointer update while looping 1 pointer focus关键位置（evenlist的start）
» 328. Odd Even Linked List 高频
http://rainykat.blogspot.com/2017/04/leetcode-328-odd-even-linked-list.html

2.partition
Ex:用merge sort来sort list ,巧用2个链表

3.用stack存倒序读数
Ex:add two number, palindrome
 https://leetcode.com/problems/add-two-numbers-ii/

➤ 普通iteration
 » 61. Rotate List
http://rainykat.blogspot.com/2017/05/leetcode-61-rotate-listlinkedlist.html 

➤ Recursive 解法
»  83.82.Remove Duplicates from Sorted List I/II
http://rainykat.blogspot.com/2017/03/8384remove-duplicates-from-sorted-list.html
»  83. Remove Duplicates from Sorted List
head.next接的是下一没有duplicates的list

public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null)return head;
        ListNode nextN = head.next;
        head.next = deleteDuplicates(head.next);
        //[0,1,1,2,5] head: 2,1,1,0 vs nextN: 5,2,1,1 -- this way from end to start
        if(nextN.val == head.val){//skip dup
            head.next = nextN.next;
            nextN = nextN.next;
        }
        return head;
    }

Loop/Iterative List 题集
» 160. Intersection of Two Linked Lists 各大家
到两个list长度相同的点开始走，找交叉点
http://rainykat.blogspot.com/2017/01/leetcode-160-intersection-of-two-linked.html
»  369. Plus One Linked List(two pointer) G家
http://rainykat.blogspot.com.tr/2017/01/leetcodeg-369-plus-one-linked-listtwo.html
» 92. Reverse Linked List II (Iteration) 
http://rainykat.blogspot.com/2017/01/leetcodef-92-reverse-linked-list-ii.html
Recursion -- O(n) time for n depth, O(n) space for stack
» 22. Merge Two Sorted List(can also iterative) Amazon LinkedIn Apple Microsoft
https://leetcode.com/problems/merge-two-sorted-lists/ 

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null)return l2;
        if(l2==null)return l1;
        if(l1.val<l2.val){
            l1.next = mergeTwoLists(l1.next,l2);//l1小就取l1,接着merge l2和l1之后的
            return l1;
        }else{
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }    
 }

» 148. Sort List(上题+merge sort)
http://rainykat.blogspot.com.tr/2017/01/leetcode-148-sort-list-mergesort.html 
» 24. Swap Nodes in Pairs 微软 Bloomberg Uber 
https://leetcode.com/problems/swap-nodes-in-pairs/ 

public class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null||head.next==null)return head;
        ListNode nextN = head.next;
        head.next = swapPairs(nextN.next);
        nextN.next = head;
        return nextN;
    }
}

» 83. Remove duplates in LinkedList
Link: https://leetcode.com/problems/remove-duplicates-from-sorted-list/

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null){ return head;}
        head.next = deleteDuplicates(head.next);
        if(head.val==head.next.val){
            head=head.next;//means skip one node             
        }
        return head;
    }
}
 
//sample output 
3&3 

* 

2&3

1&2 

1&1 

*

---

» 203.Remove Linked List Elements - 类似上题
https://leetcode.com/problems/remove-linked-list-elements/ 

public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head==null){return head;}//base case different,list can be empty
        head.next = removeElements(head.next,val);//head.next from last num to 1st
        
        if(head.val == val){
            head = head.next;
        }
        return head;
    }
}

---

 » 206. Reverse LinkedList 各大家的基础题
https://leetcode.com/problems/reverse-linked-list/ 

Recurrsion 
每次回溯把nextnode连到head，head连到null

public class Solution {
    public ListNode reverseList(ListNode head) {
        if (head==null||head.next==null){return head;}
        ListNode nextnode = head.next;
        ListNode newhead = reverseList(head.next);//last node in list
        nextnode.next=head;
        head.next= null;
        return newhead;
    }
}

Iterative:
注意最后是在head=null，所以返回prev（即newhead）

public class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null){ return head;}
        ListNode prev = null;
        while(head!=null){
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;//prev is newhead, head is null
    }
}

---

Interchange LinkedList Nodes
Given a singly linked list: 1->2->3->4->5 
Change it to 1->5->2->4->3 using O(1) space
https://leetcode.com/problems/reverse-linked-list-ii/