我要好offer之 链表大总结

单链表是一种递归结构，可以将单链表看作特殊的二叉树(我把它叫做一叉树)

单链表的定义：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

1. O(1)时间删除结点

ListNode* DeleteNode(ListNode* pHead, ListNode* deletedNode) {
    assert(pHead != NULL && deletedNode != NULL);
    ListNode newHead(-1);
    newHead.next = pHead;
    if (pHead == deletedNode) {
        newHead->next = pHead->next;
        delete deletedNode;
        deketedNode = NULL;
        return newHead.next;
    } else {
        if (deleteNode->next == NULL) {
            ListNode* cur = pHead;
            while (cur->next != deleteNode) {
                cur = cur->next;
            }
            cur->next = NULL;
            delete deletedNode;
            deletedNode = NULL;
            return newHead.next;
        } else {
            ListNode* nextNode = deletedNode->next;
            deletedNode->val = nextNode->val;
            deletedNode->next = nextNode->next;
            delete nextNode;
            nextNode = NULL;
            return newHead.next;
        }
    }
}

2. 单链表反转

ListNode* ReverseList(ListNode* pHead) {
    if (pHead == NULL || pHead->next == NULL) {
        return pHead;
    }
    ListNode* tail = pHead;
    ListNode* cur = pHead->next;
    while (cur != NULL) {
        ListNode* nextNode = cur->next;
        cur->next = pHead;
        pHead = cur;
        cur = nextNode;
    }
    tail->next = NULL;
    return pHead;
}

3. 单链表倒数第k个结点

ListNode* KthNode(ListNode* pHead, int k) {
    assert(pHead != NULL && k > 0);
    ListNode* first = pHead;
    ListNode* second = pHead;
    while (first != NULL && k > 0) {
        first = first->next;
        --k;
    }
    if (first == NULL) {
        if (k == 0) {
            return pHead;
        } else {
            return NULL;
        }
    }
    while (first != NULL) {
        first = first->next;
        second = second->next;
    }
    return second;
}

4. 单链表反转部分区间

5. 单链表快速排序的一趟划分

6. 单链表去掉重复元素

7. 单链表旋转

8. 单链表成对交换节点

9. 有序单链表归并排序

10. 单链表加法运算

11. 单链表是否存在环，环的位置

12. 两个单链表的第一个公共结点

13. 单链表归并排序

class Solution {
public:
    ListNode *sortList(ListNode *head) {
        if (head == NULL || head->next == NULL) {
            return head;
        }
        
        ListNode* slow = head;
        ListNode* fast = head;
        //快慢指针找链表中间结点
        while (fast != NULL && fast->next != NULL && fast->next->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* list1 = head;
        ListNode* list2 = slow->next;
        slow->next = NULL;
        ListNode* sortList1 = sortList(list1);
        ListNode* sortList2 = sortList(list2);
        ListNode* res = mergeSortList(sortList1, sortList2);
        return res;
    }
    
    ListNode* mergeSortList(ListNode* list1, ListNode* list2) {
        if (list1 == NULL) return list2;
        if (list2 == NULL) return list1;
        ListNode newHead(-1);
        ListNode* cur = &newHead;
        ListNode* node1 = list1;
        ListNode* node2 = list2;
        while (node1 != NULL && node2 != NULL) {
            if (node1->val <= node2->val) {
                cur->next = node1;
                node1 = node1->next;
                cur = cur->next;
            } else {
                cur->next = node2;
                node2 = node2->next;
                cur = cur->next;
            }
        }
        while (node1 != NULL) {
            cur->next = node1;
            node1 = node1->next;
            cur = cur->next;
        }
        while (node2 != NULL) {
            cur->next = node2;
            node2 = node2->next;
            cur = cur->next;
        }
        return newHead.next;
    }
};