Summary

LinkedList本身就是离散型内存，靠next连接，array是连续型内存

LinkedList都是in-place的，只改动next在内存中的位置。

基本功：

1. Insert a node in sorted list

2. Remove a node from sorted list(P112)

3. Remove Nth Node From End of List(P174)

ListNode removeNthFromEnd(ListNode head, int n) {
        if(head==null || n<=0){
            return null;
        }


        ListNode dummy=new ListNode(0);
        dummy.next=head;
        ListNode fast=head;
        ListNode slow=dummy;

        for(int i=0;i<n;i++){
            if(fast==null){
                return null;
            }
            fast=fast.next;
        }

        while(fast!=null){
            fast=fast.next;
            slow=slow.next;
        }

        slow.next=slow.next.next;
        return dummy.next;
    }

1. Reverse a LinkedList

    //Reverse
    public ListNode reverse1(ListNode head) {

          if(head==null || head.next==null){
              return head;
          }

          ListNode prev=null;
          ListNode curt=head;

          while(curt!=null){

              ListNode post=curt.next;
              curt.next=prev;
              prev=curt;
              curt=post;                        
          }

          return  prev;
 }


    public ListNode reverse2(ListNode head) {

            ListNode prev = null;
            while (head != null) {
                ListNode temp = head.next;
                head.next = prev;
                prev = head;
                head = temp;
            }
            return prev;
  }
  //怎么逆转一个单链表。其实O(n)就可以了。第一个肯定是last one。然后我们每遍历到一个node，就把它放到最链表的首位，
  //最后一个么，最后就成为第一个了。下面是一个简单逆转链表的程序。
  //pre一直在head之前的位置
  //last不变始终是original head.
  //变得只有current,一直在向后移动

          ListNode dummy = new ListNode(0);
          dummy.next = head;
          ListNode pre = dummy;
          ListNode cur = head.next;
          ListNode last = head;
          while(cur != null){
              last.next = cur.next;
              cur.next = pre.next;
              pre.next = cur;
             cur = last.next;
         }
         head = dummy.next;

1. Merge two LinkedList

 public ListNode merge(ListNode head1,ListNode head2){

            ListNode dummy=new ListNode(0);
            ListNode temp=dummy;

            while(head1!=null && head2!=null){

                if(head1.val<head2.val){
                    temp.next=head1;
                    head1=head1.next;
                }
                else{
                    temp.next=head2;
                    head2=head2.next;               
                }

                temp=temp.next;//caution
            }

            if(head1!=null){
                temp.next=head1;
            }
            if(head2!=null){
                temp.next=head2;
            }


            return dummy.next;

        }

1. Middle of LinkedList(错开一个位置，才能保证恰好在中间，不然奇数个node，slow会指在middle右边一个位置)

 public ListNode middleNode(ListNode head) { 

            if(head==null){
                return null;
            }

            ListNode slow=head;
            ListNode fast=head.next;

            while(fast!=null && fast.next!=null){
                fast=fast.next.next;
                slow=slow.next;
            }

            return slow;
        }

Detect cyclic LinkedList

//Detect cycle (find the first node in loop)
     public ListNode detectCycle(ListNode head) {  

            ListNode slow = head;
            ListNode fast = head;

            while (true) {
                if (fast == null || fast.next == null) {
                    return null;    //遇到null了，说明不存在环
                }
                slow = slow.next;
                fast = fast.next.next;
                if (fast == slow) {
                    break;    //第一次相遇在Z点
                }
            }

            slow = head;    //slow从头开始走，
            while (slow != fast) {    //二者相遇在Y点，则退出
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }

Get length of LinkedList

 private int getLength(ListNode head) {
            int length = 1;
            while (head.next != null) {
                length ++;
                head = head.next;
            }
            return length;
        }

Find the tail

ListNode current=root;
while(current.next!=null){
    current=current.next;
    }

Linked List Cycle I II

https://siddontang.gitbooks.io/leetcode-solution/content/linked_list/linked_list_cycle.html

http://www.cnblogs.com/hiddenfox/p/3408931.html

I: 单纯判断链表中有没有环：用两个快慢指针fast=head.next; slow=head; 看会不会相遇

II：找到环的入口点

可用loop解决的问题（注意这里fast,slow都从head开始）

1.环的长度是多少？

2.如何将有环的链表变成单链表？（解除环）

3.如何判断两个单链表是否有交点？如何找到第一个交点？

（Y为环的第一个点，Z是fast,slow第一次相遇的点）

Solution for 1.环的长度

1>第一相遇后，让fast,slow继续走，记录下下次相遇时环走了几次。

fast第二次到Z时，fast走了一圈，slow半圈。

fast第三次到Z时，fast走了两圈，slow一圈，正好有在Z相遇。

2>第一次相遇后，fast不走，让slow走，下次相遇时环的长度。

3>(Easiest)第一次相遇时slow走了a+b, fast走了a+b+c, 因为fast速度是slow的两倍，所以2(a+b)=a+b+c+b

所以a=c

环的长度L=a+b=b+c, 到第一次相遇，slow经过的长度就是环的长度L.

Solution for 2: 解除环变成单链表

将C段中Y之前的点与Y切断即可。

Solution for 3: 判断两个单链表是否有交点，有的话第一个交点在哪里

step 1:先判断两个链表是否有环，若一个有环一个没环 ->不相交

step 2:都没环，判断其尾部是不是相等

step 3:都有环，判断一个链表上的Z点是否在另一个链表上。

方法二（recommend）:让L1 tail.next= L2.head

判断是否有环，有环就有交点。

找到第一个相交的点：

求出 L1 L2的长度，若L1<L2,用fast slow分别从头部开始走，L2先走（L2-L1）步，然后在一起走，直到相遇。

Solution for LinkedList Cycle II (P103)--找到Y点

因为a=c,让两个指针分别从x(head),z(slow)开始走，每次走一步，正好在Y相遇-

Remove Duplicates from sorted List I II

P112 :不会换head

P113: 可能换head,要用dummy node 并且遇到重复的要一次性删完

Doubly linked list node removal

Given a doubly linked list and an integer, write a function that removes the first occurrence of that

integer from the list.

We first iterate over the linked list until we find a node with the given target value. We then update the

previous pointer in the next node to point to the node previous to the current node. We then update

the next pointer in the previous node to point to the next node of the current pointer. Now we have

effectively cut the current node out of the list.

public class Solution {
2. public static void removeTargetNode(Node head, int target) {
3. Node current = head;
4. while (current != null) {
5.  if (current.value == target) {
6.    if (current.next != null)
7.        current.next.previous = current.previous;
8.    if (current.previous != null)
9.        current.previous.next = current.next;
10.  break;
11. }
12.  current = current.next;
13. }
14. }

Finding cycles in singly linked lists(P102)

Given a singly linked list, write a function to determine if the linked list contains a cycle.

Linked list integer addition(P167,221)

Given two integers represented as linked lists, write a function that returns a linked list representing

the sum of the two integers. The digits stored in the linked list are in reverse order (least significant

digit to most significant digit). For example if the input were (1 ⇢ 5 ⇢ 8) + (1 ⇢ 2 ⇢ 3), the result would

be (2 ⇢ 7 ⇢ 1 ⇢ 1) which represents 851 + 321 = 1172.

单链表：

单链表有很多巧妙的操作，本文就总结一下单链表的基本技巧，每个技巧都对应着至少一道算法题：

1、合并两个有序链表 LeetCode 21

2、合并 k 个有序链表 LeetCode 23

3、寻找单链表的倒数第 k 个节点 LeetCode 19

4、寻找单链表的中点

5、判断单链表是否包含环并找出环起点

6、判断两个单链表是否相交并找出交点

这些解法都用到了双指针技巧，所以说对于单链表相关的题目，双指针的运用是非常广泛的，下面我们就来一个一个看