分组

328. Odd Even Linked List

序号为奇数的在前，偶数的在后，每一半相对顺序不变。

class Solution {public:    ListNode* oddEvenList(ListNode* head) {        if(!head) return NULL;                int index = 1;        ListNode pseudoHeadOfNewList = ListNode(0);        ListNode pseudoHeadOfOldList = ListNode(0);        pseudoHeadOfOldList.next = head;                ListNode *pn = &pseudoHeadOfNewList;        ListNode *prePo = &pseudoHeadOfOldList;        ListNode *po = pseudoHeadOfOldList.next;        ListNode *next = NULL;                while(po) {            next = po->next;            if(index & 1) {                pn = pn->next = po;                prePo->next = po->next;            } else {                prePo = po;            }            po = next;            ++index;        }                pn->next = pseudoHeadOfOldList.next;        return pseudoHeadOfNewList.next;    }};

725. Split Linked List in Parts

将链表分为大小差不超1的k组。

class Solution {public:    int listLength(ListNode *head) {        int cnt = 0;        for(ListNode *p = head; p; p = p->next) {            ++cnt;        }        return cnt;    }        vector
    
      splitListToParts(ListNode* root, int k) {        vector
     
       ans;        if(k <= 0) return ans;                int length = listLength(root);        int lengthOfPart = length / k;        int mod = length % k;        ListNode *p = root;                for(; k && p; --k) {            ans.push_back(p);            for(int i = lengthOfPart-(mod <= 0); i > 0; --i)                p = p->next;            ListNode *next = p->next;            p->next = NULL;            p = next;            --mod;        }        for(; k; --k)            ans.push_back(NULL);        return ans;    }};
     
    

86. Partition List

将链表分为小于x的部分和大于等于x的部分，

class Solution {public:    ListNode* partition(ListNode* head, int x) {        if(!head || !head->next) return head;                ListNode pseudoHeadOfNewList = ListNode(0);        ListNode *pNew = &pseudoHeadOfNewList;                ListNode pseudoHeadOfOldList = ListNode(0);        pseudoHeadOfOldList.next = head;        ListNode *preOld = &pseudoHeadOfOldList;                for(ListNode *pOld = head, *next = NULL; pOld; pOld = next) {            next = pOld->next;            if(pOld->val < x) {                preOld->next = pOld->next;                pNew = pNew->next = pOld;            } else {                preOld = pOld;            }        }                pNew->next = pseudoHeadOfOldList.next;        return pseudoHeadOfNewList.next;    }};

删除

237. Delete Node in a Linked List

给指向一个链表节点的指针，删除该节点。将后序的元素向前复制一位解决。

class Solution {public:    void deleteNode(ListNode* node) {        if(!node) return;                ListNode *pre = NULL;        ListNode *p = node;                while(p->next) {            p->val = p->next->val;            pre = p;            p = p->next;        }                delete p;        pre->next = NULL;    }};

83. Remove Duplicates from Sorted List

删除重复元素，每个元素仅保留一份。

class Solution {public:    ListNode* deleteDuplicates(ListNode* head) {        for(ListNode *p = head; p; p = p->next) {            while (p->next && p->val == p->next->val) {                ListNode *toDeleteNode = p->next;                p->next = p->next->next;                delete toDeleteNode;            }        }        return head;    }};

82. Remove Duplicates from Sorted List II

删除重复元素，仅保留没有重复的元素。

class Solution {public:    ListNode* deleteDuplicates(ListNode* head) {        if(!head || !head->next)            return head;                ListNode pseudoHead = ListNode(0);        pseudoHead.next = head;        ListNode *pre = &pseudoHead;        ListNode *p = head;                while(p && p->next) {            if(p->val != p->next->val) {                pre = p;                p = p->next;            } else {                int val = p->val;                while(p && p->val == val) {                    pre->next = p->next;                    delete p;                    p = pre->next;                }            }        }        return pseudoHead.next;    }};

203. Remove Linked List Elements

删除指定值的元素。

class Solution {public:    ListNode* removeElements(ListNode* head, int val) {        if(!head) return NULL;                ListNode pseudoHead = ListNode(0);        pseudoHead.next = head;                ListNode *pre = &pseudoHead;        ListNode *p = pseudoHead.next;        ListNode *next = NULL;                while(p) {            next = p->next;            if(p->val == val) {                pre->next = p->next;                delete p;            } else {                pre = p;            }            p = next;        }        return pseudoHead.next;    }};

双指针

19. Remove Nth Node From End of List

删除倒数第n个节点，快指针先走n个节点，慢指针再开始走，当p2指向NULL时，慢指针指向需要删的元素。

class Solution {public:    ListNode* removeNthFromEnd(ListNode* head, int n) {        if(!head) return NULL;                ListNode pseudoHead = ListNode(0);        pseudoHead.next = head;                ListNode *preP1 = &pseudoHead;        ListNode *p1 = head, *p2 = head;                for(int i = 0; i < n; ++i)            p2 = p2->next;                while(p2) {            preP1 = p1;            p1 = p1->next;            p2 = p2->next;        }                preP1->next = p1->next;        delete p1;        return pseudoHead.next;    }};

141. Linked List Cycle

判断一个链表是否有环。

class Solution {public:    bool hasCycle(ListNode *head) {        ListNode *p1 = head, *p2 = head;                while(p2 && p2->next) {            p1 = p1->next;            p2 = p2->next->next;            if(p1 == p2) return true;        }        return false;    }};

142. Linked List Cycle II

判断一个链表是否有环，若有返回环的起点，否则返回NULL。

class Solution {public:    ListNode *detectCycle(ListNode *head) {        ListNode *p1 = head;        ListNode *p2 = head;                while(p2 && p2->next) {            p1 = p1->next;            p2 = p2->next->next;            if(p1 == p2) {                ListNode *p = head;                while(p != p1) {                    p = p->next;                    p1 = p1->next;                }                return p;            }        }        return NULL;    }};

逆序

206. Reverse Linked List

class Solution {public:    ListNode* reverseList(ListNode* head) {        if(!head) return NULL;                ListNode *p = head;        ListNode *pre = NULL;        ListNode *next = NULL;                while(p) {            next = p->next;            p->next = pre;            pre = p;            p = next;        }        return pre;    }};

92. Reverse Linked List II

将链表的第m个到第n个节点倒序。

class Solution {public:    // 倒序从head开始的n个节点，返回新的头节点    ListNode* reverseNodes(ListNode *head, int n) {        if(!head) return head;                ListNode *p = head;        ListNode *pre = NULL;        ListNode *next = NULL;                for(int i = 0; i < n; ++i) {            next = p->next;            p->next = pre;            pre = p;            p = next;        }        head->next = p; // 只是多加这一行，和参数n        return pre;    }        ListNode* reverseBetween(ListNode* head, int m, int n) {        if(!head || !head->next || m >= n)            return head;                ListNode pseudoHead = ListNode(0);        pseudoHead.next = head;        ListNode *pre = &pseudoHead;                    for(int i = 1; i < m; ++i)            pre = pre->next;                pre->next = reverseNodes(pre->next, n-m+1);        return pseudoHead.next;    }};

25. Reverse Nodes in k-Group

将链表中的元素每k个一组倒序。

class Solution {public:    int listLength(ListNode *head) {        int cnt = 0;        for(ListNode *p = head; p; p = p->next)            ++cnt;        return cnt;    }    ListNode* reverseNodes(ListNode *head, int n) {        if(!head) return head;        ListNode *p = head;        ListNode *pre = NULL;        ListNode *next = NULL;        for(int i = 0; i < n; ++i) {            next = p->next;            p->next = pre;            pre = p;            p = next;        }        head->next = p;        return pre;    }    ListNode* reverseKGroup(ListNode* head, int k) {        int length = listLength(head);        if(length < k) return head;        ListNode dummy(0);        dummy.next = head;        ListNode *pre = &dummy;        for(int i = 0; i + k <= length; i += k) {            pre->next = reverseNodes(pre->next, k);            for(int j = k; j > 0 && pre; --j)                pre = pre->next;        }        return dummy.next;    }};

234. Palindrome Linked List

判断链表是否是回文的，将后一半逆序后，和前一半比较。

class Solution {public:    ListNode* reverse(ListNode *head) {        if(!head) return NULL;                ListNode *p = head;        ListNode *pre = NULL;         ListNode *next = NULL;                while(p) {            next = p->next;            p->next = pre;            pre = p;            p = next;        }        return pre;    }        bool isPalindrome(ListNode* head) {        if (!head || !head->next)            return true;        int cnt = 0;        bool ret = true;        ListNode *prep1, *p1, *p2, *beforeRightHalf, *afterReverse;                p1 = p2 = head;        beforeRightHalf = afterReverse = prep1 = NULL;                while(p2 && p2->next) {            prep1= p1;            p1 = p1->next;            p2 = p2->next->next;            cnt += 2;        }                if(p2) ++cnt;        beforeRightHalf = (cnt & 1) ? p1 : prep1;                afterReverse = reverse(beforeRightHalf->next);        p1 = head, p2 = afterReverse;                while(p2) {            if(p1->val != p2->val) {                ret = false;                break;            }            p1 = p1->next;            p2 = p2->next;        }                beforeRightHalf->next = reverse(afterReverse);        return ret;    }};

143. Reorder List

给链表 L: L0→L1→…→Ln-1→Ln,

返回形式 : L0→Ln→L1→Ln-1→L2→Ln-2→…

比如：{1,2,3,4} 返回 {1,4,2,3}

将后一半逆序后，和前一半组合。

class Solution {public:    ListNode* reverse(ListNode *head) {        if(!head) return head;        ListNode *p = head;        ListNode *pre = NULL;        ListNode *next = NULL;        while(p) {            next = p->next;            p->next = pre;            pre = p;            p = next;        }        return pre;    }    ListNode *beforeCenter(ListNode *head) {        ListNode *pre = NULL, *p1 = head, *p2 = head;        while(p2 && p2->next) {            pre = p1;            p1 = p1->next;            p2 = p2->next->next;        }        return pre;    }    void reorderList(ListNode* head) {        if(!head || !head->next) return;                ListNode *beforeMid = beforeCenter(head);        beforeMid->next = reverse(beforeMid->next);        ListNode *left = head;        ListNode *right = beforeMid->next;        beforeMid->next = NULL;        ListNode dummy(0);        dummy.next = head;        ListNode *p = &dummy;        ListNode *p1 = left;        ListNode *p2 = right;        while(p1 && p2) {            ListNode *next1 = p1->next;            ListNode *next2 = p2->next;            p = p->next = p1;            p = p->next = p2;            p1 = next1;            p2 = next2;        }        p->next = p2;    }};

排序

147. Insertion Sort List

插入排序。

class Solution {public:    ListNode* insertionSortList(ListNode* head) {        if(!head || !head->next) return head;                ListNode pseudoHead = ListNode(0);        pseudoHead.next = head;                ListNode *pre = &pseudoHead;                for(ListNode *p = head, *next = NULL; p; p = next) {            next = p->next;                        if(pre != &pseudoHead && p->val < pre->val) {                pre->next = p->next;                                ListNode *q = &pseudoHead;                while(q->next && q->next->val <= p->val)                    q = q->next;                                p->next = q->next;                q->next = p;            } else {                pre = p;            }        }        return pseudoHead.next;    }};

21. Merge Two Sorted Lists

合并两个有序的链表。

class Solution {public:    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {        ListNode pseudoHead(0);        ListNode *p = &pseudoHead;        ListNode *p1 = l1;        ListNode *p2 = l2;                while(p1 && p2) {            if(p1->val < p2->val) {                p = p->next = p1;                p1 = p1->next;            } else {                p = p->next = p2;                p2 = p2->next;            }        }        p->next = p1 ? p1 : p2;        return pseudoHead.next;    }};

23. Merge k Sorted Lists

合并k个有序链表，分治解决。

class Solution {public:    ListNode* mergeKLists(vector
    
     & lists) {        return mergeKListsHelper(lists.begin(), lists.size());    }        ListNode* mergeKListsHelper(vector
     
      ::iterator it, int k) {        if(k <= 0) {            return NULL;        } else if(k == 1) {            return *it;        } else if(k == 2) {            return merge(it[0], it[1]);        } else {            int h = k >> 1;            ListNode *leftHalf = mergeKListsHelper(it, h);            ListNode *rightHalf = mergeKListsHelper(it+h, k-h);            return merge(leftHalf, rightHalf);        }    }        ListNode* merge(ListNode *la, ListNode *lb) {        ListNode dummyHead(0);        ListNode *p = &dummyHead;        ListNode *pa = la;        ListNode *pb = lb;                while(pa && pb) {            if(pa->val <= pb->val) {                p = p->next = pa;                pa = pa->next;            } else {                p = p->next = pb;                pb = pb->next;            }        }        p->next = pa ? pa : pb;        return dummyHead.next;    }};
     
    

148. Sort List

以O(nlgn)排序链表，这里使用归并排序，快速排序见：

class Solution {public:    ListNode* beforeCenter(ListNode *head) {        ListNode *preP1 = NULL, *p1 = head, *p2 = head;        while(p2 && p2->next) {            preP1 = p1;            p1 = p1->next;            p2 = p2->next->next;        }        return preP1;    }    ListNode* merge(ListNode *left, ListNode *right) {        ListNode dummy = ListNode(0);        ListNode *p = &dummy;        ListNode *p1 = left;        ListNode *p2 = right;        while(p1 && p2) {            if(p1->val <= p2->val) {                p = p->next = p1;                p1 = p1->next;            } else {                p = p->next = p2;                p2 = p2->next;            }        }        p->next = p1 ? p1 : p2;        return dummy.next;    }    ListNode* sortList(ListNode* head) {        if(!head || !head->next)            return head;        ListNode *mid = beforeCenter(head);        ListNode *right = mid->next;        mid->next = NULL;        ListNode *left = sortList(head);        right = sortList(right);        return merge(left, right);    }};

其他

24. Swap Nodes in Pairs

交换相邻元素。

class Solution {public:    ListNode* swapPairs(ListNode* head) {        if(!head || !head->next) return head;                ListNode pseudoHead = ListNode(0);        pseudoHead.next = head;                ListNode *pre = &pseudoHead;        ListNode *p = pseudoHead.next;        ListNode *next1 = NULL;        ListNode *next2 = NULL;                while(p && p->next) {            next1 = p->next;            next2 = p->next->next;            pre->next = next1;            next1->next = p;            p->next = next2;            pre = p;            p = next2;        }        return pseudoHead.next;    }};

109. Convert Sorted List to Binary Search Tree

将一个链表转换成二叉树。

class Solution {public:    TreeNode* sortedListToBST(ListNode* head) {        return sortedListToBSTHelper(head, NULL);    }private:    ListNode* listCenter(ListNode *head, ListNode *tail) {        if(!head || !head->next) return head;        ListNode *p1 = head, *p2 = head;                while(p2 != tail && p2->next != tail) {            p1 = p1->next;            p2 = p2->next->next;        }        return p1;    }    TreeNode* sortedListToBSTHelper(ListNode* head, ListNode *tail) {        if(head == tail) return NULL;        ListNode *mid = listCenter(head, tail);        TreeNode *p = new TreeNode(mid->val);        p->left = sortedListToBSTHelper(head, mid);        p->right = sortedListToBSTHelper(mid->next, tail);        return p;    }};

138. Copy List with Random Pointer

class Solution {public:    RandomListNode *copyRandomList(RandomListNode *head) {        if(!head) return head;        RandomListNode *p = head;        RandomListNode *next = NULL;                while(p) {            next = p->next;            RandomListNode *newNode = new RandomListNode(p->label);            newNode->next = p->next;            p->next = newNode;            p = next;        }                for(p = head; p; p = p->next->next) {            if(p->random)                p->next->random = p->random->next;        }                RandomListNode dummyHeadOfNewList(0);        RandomListNode *pNew = &dummyHeadOfNewList;                for(p = head; p; p = next) {            next = p->next->next;            pNew = pNew->next = p->next;            p->next = next;        }        return dummyHeadOfNewList.next;    }};

61. Rotate List

循环右移链表k位。

class Solution {public:    ListNode* rotateRight(ListNode* head, int k) {        if(!head || !head->next)            return head;                int len = 1;        ListNode *oldLast = head;        while(oldLast && oldLast->next) {            ++len;            oldLast = oldLast->next;        }                k %= len;        if(!k) return head;                ListNode *newHead = head;        ListNode *newLast = NULL; // pre new head        for(int i = len - k; i > 0; --i) {            newLast = newHead;            newHead = newHead->next;        }        oldLast->next = head;        newLast->next = NULL;        return newHead;    }};

2. Add Two Numbers

class Solution {public:    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {        char up = 0;        ListNode head(0), *p = &head;        ListNode *p1 = l1, *p2 = l2;        for(; p1 && p2; p1=p1->next, p2=p2->next) {            p = p->next = new ListNode(p1->val + p2->val + up);            up = p->val / 10;            p->val %= 10;        }        for(ListNode *p3 = p1 ? p1 : p2; p3; p3 = p3->next) {            p = p->next = new ListNode(p3->val + up);            up = p->val / 10;            p->val %= 10;        }        if(up) {            p = p->next = new ListNode(up);        }        return head.next;    }};

445. Add Two Numbers II

class Solution {public:    ListNode *reverse(ListNode *head) {        if(!head) return NULL;                ListNode *pre = NULL;                for(ListNode *p = head, *next = NULL; p; p = next) {            next = p->next;            p->next = pre;            pre = p;        }        return pre;    }        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {        ListNode *newHead1 = reverse(l1);        ListNode *newHead2 = reverse(l2);        ListNode pseudoHead = ListNode(0);                int up = 0;                ListNode *p1 = newHead1, *p2 = newHead2, *p = &pseudoHead;                while(p1 && p2) {            p = p->next = new ListNode(up + p1->val + p2->val);            up = p->val / 10;            p->val %= 10;            p1 = p1->next;            p2 = p2->next;        }                p1 = p1 ? p1 : p2;        while(p1) {            p = p->next = new ListNode(up + p1->val);            up = p->val / 10;            p->val %= 10;            p1 = p1->next;        }                if(up) {            p->next = new ListNode(up);        }        reverse(newHead1);        reverse(newHead2);        return reverse(pseudoHead.next);    }};