Leetcode - Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

[Thoughts]: 这好像是CC150上的题，后面还有个followup

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode newhead = new ListNode(-1);
        ListNode p = newhead;
        int carry = 0;
        while(l1!=null || l2!=null || carry!=0){
            if(l1!=null){
                carry += l1.val;
                l1=l1.next;
            }
            if(l2!=null){
                carry += l2.val;
                l2=l2.next;
            }
            
            p.next = new ListNode(carry%10);
            p = p.next;
            carry = carry/10;
        }
        return newhead.next;
    }
}

Leetcode - Remove Nth Node From End of List

Given a linked list, remove the n^th node from the end of list and return its head.
For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.
[Thoughts]:

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode newhead = new ListNode(-1);
        newhead.next = head;
        ListNode pre = newhead;
        while(n>1 && head!=null){
            head = head.next;
            n--;
        }
        if(head==null) return null;
        while(head.next!=null){
            pre = pre.next;
            head = head.next;
        }
        pre.next = pre.next.next;
        return newhead.next;
    }
}

Leetcode - Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

[Thoughts]: 就是不把自己转晕就可以了，拿一个例子试一试

public class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null || head.next==null) return head;
        ListNode dummyhead = new ListNode(-1);
        dummyhead.next = head;
        
        ListNode pre = dummyhead;
        ListNode cur = head;
        while(cur!=null && cur.next!=null){
            ListNode next = cur.next;
            ListNode temp = cur.next.next;
            next.next = cur;
            pre.next = next;
            pre = cur;
            cur = temp;
        }
        pre.next = cur;
        return dummyhead.next;
    }
}

Leetcode - Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5

[Thoughts]:

public class Solution {//03
    public ListNode reverseKGroup(ListNode head, int k) {
        if(k==1) return head;
        ListNode newhead = new ListNode(-1);
        newhead.next = head;
        ListNode pre = newhead;
        
        int i = 0;
        while(head!=null){
            i++; 
            if(i%k==0){
                pre = reverse(pre, head.next);
                head = pre.next;
            }else
                head = head.next;
        }
        return newhead.next;
    }
    public ListNode reverse(ListNode pre, ListNode end){
        ListNode last = pre.next;//last = 1
        ListNode cur = last.next;// cur = 2
        while(cur!=end){
            last.next = cur.next;//1.next = null
            cur.next = pre.next;//2.next = 1;
            pre.next = cur;// pre = 2;
            cur = last.next;// cur = null;
        }
        return last;
    }
    
   
}

Leetcode -Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

[Thoughts]:the point of this question is that K could be larger than the length of list.

public class Solution {
    public ListNode rotateRight(ListNode head, int n) {
        if(head==null || head.next ==null || n==0) return head;
        int len = 1;
        ListNode p = head;
        while(p.next!=null){
            len++;
            p = p.next;
        }
        p.next = head;
        p = head;
        
        int k = len - n%len-1;
        while(k>0){
            k--;
            p = p.next;
        }
        
        ListNode newhead = p.next;
        p.next = null;
        return newhead;
    }
}

Leetcode - Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode p1, p2, p;
        ListNode newhead = new ListNode(0);
        p1 = l1; p2 = l2; p= newhead;
        
        while(p1!=null && p2!=null){
            if(p1.val<=p2.val){
                p.next = p1;
                p1 = p1.next;
            }else{
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }
        if(p1!=null)
          p.next = p1;
        else if (p2!=null)
          p.next = p2;
        return newhead.next;
    }
}

Leetcode - Remove Duplicates from Sorted List I && II

I: Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode p = head;
        while(p!=null && p.next!=null){
            if(p.val == p.next.val)
                p.next = p.next.next;
            else
                p = p.next;
        }
        return head;
    }
}

II:Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode newHead = new ListNode(-1);
        ListNode p = newHead;
        ListNode cur = head;
        
        while(cur!=null && cur.next!=null){
            if(cur.val!=cur.next.val){
                p.next = cur;
                p = p.next;
                cur = cur.next;
            }else{
                while(cur!=null && cur.next!=null && cur.val==cur.next.val){
                    cur = cur.next;
                }
                cur = cur.next;
            }
        }
        p.next = cur;
        return newHead.next;
    }
}

Leetcode - Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

public class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode firsthead = new ListNode(-1);
        ListNode first = firsthead;
        ListNode secondhead = new ListNode(-1);
        ListNode second = secondhead;
        
        
        while(head!=null){
            if(head.val<x){
                first.next = head;
                first = first.next;
            }else{
                second.next = head;
                second = second.next;
            }
            head = head.next;
        }
        
        second.next = null; // do not forget set the last pointer of second as null;
        first.next  = secondhead.next;
        return firsthead.next;
    }
}

Linked List Cycle I && II

验证linked list是否有环，cc150原题，并且有详细的数学解释，不赘述（其实没有必要去证明，知道理论就可，嘿嘿）。

I: Given a linked list, determine if it has a cycle in it.

检测是否有环，设快慢两指针，能相遇便有环。

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow==fast) return true;
        }
        return false;
    }
}

II: Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

同I，设快慢两指针：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        //1，找到相遇点
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow==fast) break;
        }
        if(fast==null || fast.next==null ) return null;
        
        slow = head;//2，把slow挪到head。

        //3，slow从head开始，fast从相遇点开始同步走，再次相遇点便是cycle起始点。
        while(slow!=fast){
            slow = slow.next;
            fast = fast.next;
        }
        
        return slow;
        
    }
}

Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

分三步：
1， 找到list中间的点。
2，把第二部分reverse
3，把两个部分间隔串起来。

实现过程中，完成第一步后，忘记把slow挪到head了，该打！！！

public class Solution {
    public void reorderList(ListNode head) {
        if(head==null || head.next==null) return;
        //1， find the middle node of the list. 
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next!=null && fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        fast = slow.next; 
        slow.next = null;
        slow = head;//实现中忘记这一步了，哭

        //2，reverse list start with fast.
        ListNode pre = fast;
        ListNode cur = pre.next;
        while(cur!=null){
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        fast.next = null;
        fast = pre;
        //3, linked them together
        while(slow!=null && fast!=null){
            ListNode p1 = slow.next;
            ListNode p2 = fast.next;
            slow.next = fast;
            fast.next = p1;
            slow = p1;
            fast = p2;
        }
    }
}

Reverse Linked List II

[Question]:

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

[Thoughts]:
典型的linkedlist题，建立了很多指针。
如example， 如果你要转2-3-4，
1， 你要记住1(pre)，记住2（end）
2， 反转2-3-4成4-3-2， 记住5 (next)
3， 串起来, pre指向4， end指向next

    
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head==null || m==n) return head;
        ListNode newHead = new ListNode(-1);
        newHead.next = head;
        ListNode pre = newHead;
        
        int index = 1;
        while(index<m){
            index++;
            pre = pre.next;
        }
        
        ListNode end = pre.next;
        ListNode p   = pre.next;
        ListNode cur = p.next;
        ListNode next = null;
        
        while(index<n){
           next = cur.next;
           cur.next = p;
           p = cur; 
           cur = next;
           index++;
        }
        
        pre.next = p;
        end.next = next;
        
        return newHead.next;
    }
}

Reverse LinkedList

Note:

line15： 反转之后，原来链表的头next指针要设为null。

     
      if(head==null)  
        return head;  
      ListNode pre = head;  
      ListNode cur = head.next;  
      ListNode temp = null;  
    
      while(cur!=null){  
        temp = cur.next;  
        cur.next = pre;  
        pre = cur;  
        cur = temp;  
      }  
    
      head.next = null;  
      return pre;  
    

LinkedList找中间的点

很多关于LinkedList的题都会需要找中间的点， array的话可以通过index很容易就找到了，linkedlist需要用到快慢指针， 不熟练的时候总会是要想一下边界情况：

1:  ListNode function(){  
2:      if(head==null || head.next==null)  
3:        return head;  
4:      ListNode slow = head;  
5:      ListNode fast = head;  
6:      while(fast.next!=null && fast.next.next!=null){  
7:        slow = slow.next;  
8:        fast = fast.next.next;  
9:      }  
10:      return slow;  
11:  }    

如果LinkedList的长度是偶数， 如 A -> B -> C -> D,  返回 slow = B

如果是基数， 如 A -> B -> C -> D -> E,  返回 slow = C