喜刷刷: linked list

Showing posts with label linked list. Show all posts

Thursday, November 27, 2014

[LeetCode新题] Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

思路：

找链表交界，很类似Linked List Cycle II那题，方法也是类似的双指针相遇法。分两步走：

1. 如何判断两链表是否相交？

两链表相交则他们必然有共同的尾节点。所以遍历两两链表，找到各自的尾节点，如果tailA!=tailB则一定不相交，反之则相交。

2. 如何判断两链表相交的起始节点？

在第1步判断相交时可以顺带计算两链表的长度lenA和lenB。让长的链表的head先走abs(lenA-lenB)步，然后和短链表的head一起走，直到两者相遇，即为要找的节点。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(!headA || !headB) return NULL;
        int lenA = 0, lenB = 0;
        ListNode *tailA = headA, *tailB = headB;
        
        while(tailA->next) {
            tailA = tailA->next;
            lenA++;
        }
        while(tailB->next) {
            tailB = tailB->next;
            lenB++;
        }
        if(tailA!=tailB) return NULL;
        
        if(lenA>lenB) {
            for(int i=0; i<lenA-lenB; i++)
                headA = headA->next;
        }
        else {
            for(int i=0; i<lenB-lenA; i++)
                headB = headB->next;
        }
        
        while(headA!=headB) {
            headA = headA->next;
            headB = headB->next;
        }
        
        return headA;
    }
};

Wednesday, November 26, 2014

[LeetCode] LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

思路：

LRU cache数据结构的核心就是当存储空间满了，而有新的item要插入时，要先丢弃最早更新的item。这里的数据结构需要符合以下条件：

1. 要能快速找到最早更新的item。这里需要将item以更新时间顺序排序。
可选的有：queue，heap，linked list

2. 要能快速访问指定item，并且访问以后要更新它的时间顺序。
对于更新时间顺序这个操作，queue和heap要做到就很困难了。所以这点最佳的是linked list。但linked list中查找指定item需要遍历，这里可以用一个hash table来记录key与节点之间的对应。并且由于要随时更新节点位置，doubly linked list更为适用。

根据以上两点，有了以下解法。注意由于代码较长，面试时尽可能将一些基本操作写成函数。

class LRUCache{
    
    struct Node {
        int val;
        int key;
        Node *next;
        Node *prev;
        Node(int k, int v):key(k),val(v) {}
    };
    
    int maxSize;
    Node* head;
    Node* tail;
    unordered_map<int,Node*> keyToNode;
    
    void insertToEnd(int key, int value) {
        if(isFull() || keyToNode.count(key)!=0) return;
        Node *nd = new Node(key, value);
        keyToNode[key] = nd;
        if(!head) {
            head = tail = nd;
        }
        else {
            tail->next = nd;
            nd->prev = tail;
            tail = tail->next;
        }
    } 
    
    void removeHead() {
        if(!head) return;
        keyToNode.erase(head->key);
        Node *temp = head;
        if(head==tail) // only one node remain
            head = tail = NULL;
        else {
            head = head->next;
            head->prev = NULL;
        }
        delete temp;
    }

    void moveToEnd(int key) {
        // key not exist, or already at the end
        if(keyToNode.count(key)==0 || keyToNode[key]==tail) return;
        Node *nd = keyToNode[key];
        if(nd==head) {
            head = head->next;
            head->prev = NULL;
        }
        else {  // not head, not tail
            nd->prev->next = nd->next;
            nd->next->prev = nd->prev; 
        }
        
        tail->next = nd;
        nd->prev = tail;
        nd->next = NULL;
        tail = tail->next;
    }
    
public:
    LRUCache(int capacity) {
        maxSize = capacity;
        head = NULL;
        tail = NULL;
        keyToNode.clear();
    }
    
    int get(int key) {
        if(keyToNode.count(key)==0) return -1;
        moveToEnd(key);
        return keyToNode[key]->val;
    }
    
    void set(int key, int value) {
        // key already exists
        if(get(key)!=-1) {
            keyToNode[key]->val = value;
            return;
        }
        
        // key not exist, insert new node
        if(isFull()) removeHead();
        insertToEnd(key, value);
    }
    
    bool isFull() {
        return keyToNode.size()>=maxSize;
    }
};

Friday, November 21, 2014

[LeetCode] Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

思路1：priority queue

将每个list的最小节点放入一个priority queue (min heap)中。之后每从queue中取出一个节点，则将该节点在其list中的下一个节点插入，以此类推直到全部节点都经过priority queue。由于priority queue的大小为始终为k，而每次插入的复杂度是log k，一共插入过nk个节点。时间复杂度为O(nk logk)，空间复杂度为O(k)。

注意C++的STL中的priority queue默认是max heap，定义一个新的比较函数。

class Solution {
public:
    struct compNode {
        bool operator()(ListNode *p, ListNode *q) const {
            return p->val>q->val;
        }  
    };

    ListNode *mergeKLists(vector<ListNode *> &lists) {
        priority_queue<ListNode*, vector<ListNode*>, compNode> pq;
        ListNode *dummy = new ListNode(0), *tail = dummy;
        
        for(int i=0; i<lists.size(); i++) 
            if(lists[i]) pq.push(lists[i]);
            
        while(!pq.empty()) {
            tail->next = pq.top();
            tail = tail->next;
            pq.pop();
            if(tail->next) pq.push(tail->next);
        }
        
        return dummy->next;
    }
};

思路2：Merge two lists

利用合并两个list的方法，依次将每个list合并到结果的list中。这个方法的空间复杂度为O(1)，时间复杂度为：

2n + 3n + ... + kn = [(k+1)*k/2-1]*n = O(nk^2)

由于时间复杂度较大，大数据测试会超时。

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        ListNode *ret = NULL;
        for(int i=0; i<lists.size(); i++) 
            ret = merge2Lists(ret, lists[i]);
        return ret;
    }
    
    ListNode* merge2Lists(ListNode *h1, ListNode *h2) {
        ListNode *dummy = new ListNode(0), *tail = dummy;
        while(h1 && h2) {
            if(h1->val<=h2->val) {
                tail->next = h1;
                h1 = h1->next;
            }
            else {
                tail->next = h2;
                h2 = h2->next;
            }
            tail = tail->next;
        }
        tail->next = h1 ? h1 : h2;
        return dummy->next;
    }
};

思路3：二分法

类似merge sort，每次将所有的list两两之间合并，直到所有list合并成一个。如果用迭代而非递归，则空间复杂度为O(1)。时间复杂度：
2n * k/2 + 4n * k/4 + ... + (2^x)n * k/(2^x) = nk * x
k/(2^x) = 1 -> 2^x = k -> x = log2(k)
所以时间复杂度为O(nk log(k))，与方法一相同。

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        if(lists.empty()) return NULL;
        int end = lists.size()-1;
        while(end>0) {
            int begin = 0;
            while(begin<end) {
                lists[begin] = merge2Lists(lists[begin], lists[end]);
                begin++;
                end--;
            }
        }
        return lists[0];
    }
    
    ListNode* merge2Lists(ListNode *h1, ListNode *h2) {
        ListNode *dummy = new ListNode(0), *tail = dummy;
        while(h1 && h2) {
            if(h1->val<=h2->val) {
                tail->next = h1;
                h1 = h1->next;
            }
            else {
                tail->next = h2;
                h2 = h2->next;
            }
            tail = tail->next;
        }
        tail->next = h1 ? h1 : h2;
        return dummy->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

思路:

Swap Nodes in Pairs那题的升级版，算linked list指针操作题中难度最高最容易写错的之一。思路很简单，就是每次反转k个节点，如果还没反转到i<k个节点就遇到尾部了，则将这i个节点再反转回来。但要短时间内写正确却难度不小。这类题目一定要画图来验证解法是否正确。

class Solution {
public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        if(k<2) return head;
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        ListNode *p = dummy;
        while(p->next && p->next->next) {
            ListNode *prev = p->next, *cur = prev->next;
            int i=0;
            while(cur && i<k-1) {
                ListNode *temp = cur->next;
                cur->next = prev;
                prev = cur;
                cur = temp;
                i++;
            }
            
            if(i==k-1) {    // k nodes reversed
                ListNode *temp = p->next;
                p->next->next = cur;
                p->next = prev;
                p = temp;
            }
            else {  // less than k nodes reversed before reach end
                cur = prev->next;
                prev->next = NULL;
                while(cur != p->next) {
                    ListNode *temp = cur->next;
                    cur->next = prev;
                    prev = cur;
                    cur = temp;
                }
                break; 
            }
        }
        return dummy->next;
    }
};

总结：

几乎用到linked list题所有的技巧。

1. p指针总是指向每次要反转的k个节点的前一个节点。因为反转后仍然要接回这个节点之后。

2. ln8：如果p指针后没有节点或只剩一个节点了，那么整个反转结束。

3. ln11-17：尝试反转k个节点，如果遇到尾部，则提前结束。i记录了反转多少次。注意，要反转k个节点的话，实际反转指针只需要k-1次。

4. ln19-24：如果成功反转k个节点，则i=k-1。此时将反转的k个节点两头接回，并将p移动到反转后k个节点的最后一个节点处，以备继续反转之后的k个节点。

5. ln25-35：如果没能反转k个节点就遇到尾部。则逆向还原。

Thursday, November 20, 2014

[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

思路：

从l1, l2头节点开始，对应位置相加并建立新节点。用一个变量carry记录进位。注意几种特殊情况：

1. 一个链表为空

l1: NULL

l2: 1->2

sum: 1->2

2. l1, l2长度不同，且结果有可能长度超过l1, l2中的最大长度

l1: 2->2

l2: 9->9->9

sum: 1->2->0->1

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        ListNode *dummy = new ListNode(0), *p = dummy;
        int carry = 0;
        while(l1 || l2 || carry) {
            if(l1) {
                carry+=l1->val;
                l1 = l1->next;
            }
            if(l2) {
                carry+=l2->val;
                l2 = l2->next;
            }
            p->next = new ListNode(carry%10);
            carry /= 10;
            p = p->next;
        }
        return dummy->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.

思路：

和reverse linked list很像，只不过每次reverse两个节点。同样要考虑奇偶数长度的情况。并且由于头节点会变动，dummy节点又能派上用场了。

奇数：

1->2->3

2->1->3

偶数

1->2->3->4

2->1->4->3

要constant space所以不能用递归。那就用一个指针p边扫描边reverse。用一个子函数来完成reverse pair并接回原链表的操作，返回值为pair的尾部，也就是p下一个移动位置。

D->1->2->3->4

|
p

D->2->1->3->4
|

r = swapNodes(p->next)

class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        head = dummy;
        while(head) head = swapNodes(head->next);
        head = dummy->next;
        delete dummy;
        return head;
    }
    
    ListNode *swapNodes(ListNode *&head) {
        if(!head || !head->next) return NULL;
        ListNode *tail = head;
        ListNode *nextHead = head->next->next;
        head = head->next;
        head->next = tail;
        tail->next = nextHead;
        return tail;
    }
};

不用子程序也可以用三指针扫描来完成：

class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        ListNode *prev = dummy, *cur = head;
        
        while(cur && cur->next) {
            prev->next = cur->next;
            cur->next = cur->next->next;
            prev->next->next = cur;
            prev = cur;
            cur = cur->next;
        }
        
        return dummy->next;
    }
};

[LeetCode] Reverse Linked List II

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.

思路：

反转整个链表的变种，指定了起点和终点。由于m=1时会变动头节点，所以加入一个dummy头节点

1. 找到原链表中第m-1个节点start：反转后的部分将接回改节点后。

从dummy开始移动m-1步

D->1->2->3->4->5->NULL

2. 将从p = start->next开始，长度为L = n-m+1的部分链表反转。

__________

| |

| V

D->1->2<-3<-4 5->NULL

| | |

st p h0

3. 最后接回

__________

| |

| V

D->1 2<-3<-4 5->NULL

|________|

class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        if(m<1 || m>=n || !head) return head;
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        head = dummy;
        
        // move head to (m-1)th node
        for(int i=0; i<m-1; i++)
            head = head->next;
        
        // reverse list from pre with length n-m+1    
        ListNode *pre = head->next, *cur = pre->next;
        for(int i=0; i<n-m; i++) {
            ListNode *temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        
        head->next->next = cur;
        head->next = pre;
        head = dummy->next;
        delete dummy;
        return head;
    }
};

[LeetCode] 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) 找到链表后一半。
(2) 将后一半节点反转。
(3) 将后一半节点依次插入前一半。

解法实现时有不少要注意的地方：

I. 奇偶链表长度：

偶数长度：1->2->3->4

(1) 1->2->3<-4

| |

h1 h2

(2) 1->4->2->3

| |

h1 h2

奇数长度：1->2->3->4->5

(1) 1->2->3<-4<-5

| |

h1 h2

(2) 1->5->2->3<-4

| |

h1 h2

(3) 1->5->2->4->3

h1, h2

规律：如果链表长度为L，无论L是奇数还是偶数，都从第k = L/2+1 个节点起反转。

II 如何找到第k=L/2+1个节点？

可以扫描两遍，第一遍得到L，并计算k。而第二遍扫描找到节点k。而更好的方法则是采用快慢双指针的策略：f每次走两步，s每次走一步。当f到达最后一个节点(而不是NULL)时，s指向k。同样分奇偶长度来验证：

偶数长度：1->2->3->4

(1) 1->2->3->4->NULL

| |

s f

(2) 1->2->3->4->NULL

| |

s f

奇数长度：1->2->3->4->5

(1) 1->2->3->4->5->NULL

| |

s f

(2) 1->2->3->4->5->NULL

| |

s f

III 如何将后一半反转的链表节点依次插入前一半中？

(1) 用双指针left/right分别从左右两头开始向中间扫描。依次将right所指节点插入left节点后面。每次插入后，left需要移动两次。

(2) 终止条件：当right扫描到最后一个节点(left->next==NULL)时结束，而该节点就是原链表中的第k=L/2+1个节点。

由于步骤比较复杂，写的时候尽量分成子程序写。

class Solution {
public:
    void reorderList(ListNode *head) {
        ListNode *mid = findMid(head);
        ListNode *right = reverseList(mid);
        ListNode *left = head;
        
        while(right && right->next) {
            ListNode *target = right;
            right = right->next;
            target->next = left->next;
            left->next = target;
            left = left->next->next;
        }
    }
    
    ListNode *findMid(ListNode *head) {
        ListNode *fast = head;
        ListNode *slow = head;
        while(fast && fast->next) {
            fast = fast->next;
            if(fast->next) fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
    
    ListNode *reverseList(ListNode *head) {
        if(!head) return head;
        ListNode *pre = head, *cur = head->next;
        while(cur) {
            ListNode *temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        head->next = NULL;
        return pre;
    }
};

[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.

思路：

由于不要求sort，只要求partition。可以建立一个新的list l2。遍历原list l1的每个节点p。

p->val < x，保留。

p->val >= x，从l1中移出并插入l2。

由于要删除节点需要使用被删节点的前节点。所以实际写的时候考察的是p->next->val和x的比较。

class Solution {
public:
    ListNode *partition(ListNode *head, int x) {
        ListNode *h1 = new ListNode(0);
        ListNode *h2 = new ListNode(0);
        ListNode *t2 = h2;
        h1->next = head;
        head = h1;
        
        while(head->next) {
            if(head->next->val<x)   // skip node
                head = head->next;
            else {  // remove node from h1 and insert to the tail of h2
                t2->next = head->next;
                head->next = head->next->next;
                t2 = t2->next;
                t2->next = NULL;
            }
        }
        
        head->next = h2->next;
        head = h1->next;
        delete h1;
        delete h2;
        return head;
    }
};

总结：
这类头节点经常要插入、删除的题目，第一反应就是试试使用dummy头节点来简化代码。

[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.

思路：

以题中例子说明，向右转k次需要有两个操作。
1. 将原list的头尾相连。

2. 找到倒数第k+1个节点，并将它与倒数第k个节点断开。而倒数第k个节点为新的head。在1中找list的尾时已经计算出了list的总长n。从尾部开始走n-k步即为该点。

corner case：

1. k<=0 || head == NULL，直接返回。

2. k>= L，L为list总长。对于例子中的list，当k=5时旋转后又回到原来状态。所以实际旋转的次数为k%L。

class Solution {
public:
    ListNode *rotateRight(ListNode *head, int k) {
        if(k<1 || !head) return head;
        
        ListNode *p = head;
        int len=1;
        while(p->next) {    // get list length
            p = p->next;
            len++;
        }
        p->next = head;     // connect head to the tail
        k = len - k%len;
        
        while(k>0) {
            p = p->next;
            k--;
        }
        
        head = p->next;
        p->next = NULL;
    
        return head;
    }
};

Wednesday, November 19, 2014

[LeetCode] Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

思路：

这题的关键是如何track一个节点是否已经被copy了。假如我们要copy如下list，用指针p1来扫描每个节点，另一个指针p2建立copy。

______

| |

| V

1->2->3

p1扫描1时，p2复制1，以及1->next (2), 1->random (3)。之后p1, p2分别移到各自的2节点。此时我们必须得知道节点3在之前已经被复制了，并且得知道复制节点的地址。

______

| |

| V

1->2 3

所以这里可以使用一个hash table来记录原节点和复制节点的地址对应关系。这样每次要建立当前节点p的next和random前，先在hash table中查找。如果找到，则直接连接；否则建立新节点连上，并把和原节点的对应关系存入hash table中。

class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        if(!head) return NULL;
        unordered_map<RandomListNode*, RandomListNode*> ht;
        RandomListNode *p1 = head;
        RandomListNode *p2 = new RandomListNode(head->label);
        ht[head] = p2;
        while(p1) {
            if(p1->next) {
                if(ht.count(p1->next))
                    p2->next = ht[p1->next];
                else {
                    p2->next = new RandomListNode(p1->next->label);
                    ht[p1->next] = p2->next;
                }
            }
            if(p1->random) {
                if(ht.count(p1->random))
                    p2->random = ht[p1->random];
                else {
                    p2->random = new RandomListNode(p1->random->label);
                    ht[p1->random] = p2->random;
                }
            }
            p1 = p1->next;
            p2 = p2->next;
        }
        return ht[head];
    }
};

[LeetCode] Insertion Sort List

Sort a linked list using insertion sort.

思路：
拿出原list的头节点，用一个指针扫描新list直到找到插入位置，并插入。注意点：
1. 用dummy head来简化新list的头节点操作。
2. 由于插入节点需要依赖插入位置的前一节点。所以用指针p来查找新list节点时，始终用p->next来和要插入的节点比较，而不是用p来比较。
3. 注意当节点需要插入新list尾部的情况。

class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        ListNode *newHead = new ListNode(INT_MIN);
        while(head) {
            ListNode *cur = head;
            ListNode *p = newHead;
            head = head->next;
            while(p->next && p->next->val<=cur->val) 
                p = p->next;
            cur->next = p->next;
            p->next = cur;
        }
      
        head = newHead->next;
        delete newHead;
        return head;
    }
};

[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.

思路：

和merge sort中的merge过程很像。两个list l1, l2的head始终指向它们各自的最小节点，取其中更小的那个插入新的list l3中即可。直到l1, l2中任意一个节点用完，则将另一个list剩余节点插入l3最后即可。

class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode *l3 = new ListNode(-1);
        ListNode *t3 = l3;
        while(l1 && l2) {
            if(l1->val<=l2->val) {
                t3->next = l1;
                l1 = l1->next;
            }
            else {
                t3->next = l2;
                l2 = l2->next;
            }
            t3 = t3->next;
            t3->next = NULL;
        }
        
        t3->next = l1 ? l1 : l2;
        ListNode* temp = l3;
        l3 = l3->next;
        delete temp;
        return l3;
    }
};

[LeetCode] Remove Duplicates from Sorted List I, II

Remove Duplicates from Sorted List 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.

Remove Duplicates from Sorted List 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.

思路：Remove Duplicates from Sorted List I

由于list已经排序过，重复节点必相邻。由于链表指针是单向的，所以访问每个节点时，判断后一个节点是否是重复节点，如果是，则删除后一个节点。由于I中重复节点要保留一个，如果碰到重复删除后节点，则不需要考虑删除头指针的特殊情况。

class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        if(!head) return head;
        ListNode *cur = head;
        while(cur->next) {
            if(cur->val == cur->next->val) {
                ListNode *temp = cur->next;
                cur->next = temp->next;
                delete temp;
            }
            else {
                cur = cur->next;
            }
        }
        return head;        
    }
};

思路：Remove Duplicates from Sorted List II

II比I难在需要删除所有的重复节点。这里需要注意两点：
1. 头节点也可能被删除。可以使用dummy节点来简化。
2. 如果采用与I类似的思路来删除当前节点后所有的重复节点，则完成后还需要把当前节点也删除。因此需要有一个变量来记录当前节点是否有重复。

class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        ListNode *pre = dummy, *cur = head;
        bool duplicate = false;
        
        while(cur) {
            if(cur->next && cur->val==cur->next->val) {
                ListNode *temp = cur->next;
                cur->next = temp->next;
                delete temp;
                duplicate = true;
            }
            else if(duplicate) {
                pre->next = cur->next;
                delete cur;
                cur = pre->next;
                duplicate = false;
            }
            else {
                pre = cur;
                cur = cur->next;
            }
        }
        
        head = dummy->next;
        delete dummy;
        return head;
    }
};