链表

一、目录

• 206.反转链表
• 24.两两交换链表中的节点
• 25.K 个一组翻转链表（hard）
• 234.回文链表
• 160.相交链表
• 23.合并K个排序链表（hard）

二、题目

160.相交链表

方法1：哈希表
方法2：对齐求解

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    // 获得两个链表长度
    int lens1 = 0, lens2 = 0;
    
    for (ListNode* temp = headA; temp; lens1++, temp = temp->next) ;
    for (ListNode* temp = headB; temp; lens2++, temp = temp->next) ;
    
    // 长的先走
    if (lens1 > lens2) {
        for (int i=0; i<lens1-lens2; i++, headA=headA->next) ;
    }else{
        for (int i=0; i<lens2-lens1; i++, headB=headB->next) ;
    }
    
    // 一起走
    while (headA && headB) {
        if (headA == headB) return headA;
        
        headA=headA->next;
        headB=headB->next;
    }
    return NULL;
}

206.反转链表

非递归版本

ListNode* reverseList(ListNode* head) {
    ListNode* pre = NULL;
    ListNode* cur = head;
    
    while (cur) {
        ListNode* temp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
}

递归版本

ListNode* helper(ListNode* cur, ListNode* pre) {
    if (!cur) return cur;
    
    ListNode* temp = cur->next;
    cur->next = pre;
    return helper(temp, cur);
}

24.两两交换链表中的节点

步骤：

• 需要交换的节点
• 交换
• 连接前后
• 重置节点

ListNode* swapPairs(ListNode* head) {
    if (!head) return head;
    
    ListNode* dummy = new ListNode();
    dummy->next = head;
    
    ListNode* pre = dummy;
    ListNode *first, *second;
    while (pre->next && pre->next->next) {
        // 需要交换的节点
        first = pre->next;
        second = first->next;
        
        // 交换
        ListNode* temp = second->next;
        second->next = first;
        
        // 连接前后
        pre->next = second;
        first->next = temp;
        
        // 重置节点
        pre = first;
    }
    return dummy->next;
}

25.K 个一组翻转链表

该题是上面两题的融合。基本思路还是上面两个题。

步骤：

• 需要反转的子链表
• 反转
• 连接前后
• 重置节点

ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode* dummy = new ListNode();
    dummy->next = head;
    
    // 先求出长度
    int lens = 0;
    for (ListNode* temp = head; temp; lens++, temp=temp->next);
    
    ListNode* prevTail = dummy;
    ListNode *pre, *cur, *subTail;
    while ((lens / k) > 0) {
        // 需要反转的子链表
        pre = prevTail->next;
        cur = pre->next;
        subTail = pre;
        
        // 反转以pre为首结点、长度为k的子链表
        for (int i=1; i<k; i++) {
            ListNode* temp = cur->next;
            cur->next = pre;
            
            pre = cur;
            cur = temp;
        }
        
        // 连接前后
        prevTail->next = pre;
        subTail->next = cur;
        
        // 重置节点
        prevTail = subTail;
        
        lens -= k;
    }
    return dummy->next;
}

234.回文链表

步骤：

• 1.使用快慢指针找到链表中点。（这里需要特殊处理一下）
• 2.反转后半段
• 3.判断两个链表

bool isPalindrome(ListNode* head) {
    ListNode *slow, *fast;
    slow = fast = head;
    
    // 1.使用快慢指针找到链表中点。
    while (fast) {
        slow = slow->next;
        fast = fast->next ? fast->next->next : fast->next;
    }
    
    // 2.反转后半部分。
    ListNode *prev = nullptr;
    while (slow) {
        ListNode* temp = slow->next;
        slow->next = prev;
        
        prev = slow;
        slow = temp;
    }
    
    // 3.判断两个链表
    while (head && prev) {
        if (head->val != prev->val) {
            return false;
        }
        head = head->next;
        prev = prev->next;
    }
    return true;
}

23.合并K个排序链表

方法1：两两归并链表
时间复杂度：O(k*N)
空间复杂度：O(k)

ListNode* mergeTwoLists(ListNode* node1, ListNode* node2) {
    ListNode* dummy = new ListNode();
    ListNode* cur = dummy;

    while (node1 && node2) {
        if (node1->val < node2->val) {
            cur->next = node1;
            node1 = node1->next;
            cur = cur->next;
        }else{
            cur->next = node2;
            node2 = node2->next;
            cur = cur->next;
        }
    }
    cur->next = node1 ? node1 : node2;
    return dummy->next;
}

ListNode* mergeKLists(vector<ListNode*>& lists) {
    ListNode* ans = NULL;

    for (ListNode* t: lists) {
        ans = mergeTwoLists(ans, t);
    }
    return ans;
}

方法2：分治归并

ListNode* merge(vector<ListNode*>& lists, int l, int r){
    if (l == r) return lists[l];
    if (l > r) return nullptr;
    
    int mid = (l + r) / 2;

    ListNode* left = merge(lists, l, mid);
    ListNode* right = merge(lists, mid + 1, r);

    return mergeTwoLists(left, right);
}

ListNode* mergeKLists(vector<ListNode*>& lists){
    return merge(lists, 0, lists.size() - 1);
}

方法3：排序
时间复杂度：O(n log n)
空间复杂度：O(n)

ListNode* mergeKLists3(vector<ListNode*>& lists) {
    vector<ListNode*> nums;
    
    for (ListNode* list: lists) {
        while (list) {
            nums.push_back(list);
            list = list->next;
        }
    }
    if (nums.empty()) return nullptr;
    
    auto cmp = [](ListNode*& l, ListNode*& r) { return l->val < r->val; };
    sort(nums.begin(), nums.end(), cmp);
    
    for (int i=0; i<nums.size()-1; i++) {
        nums[i]->next = nums[i+1];
    }
    nums.back()->next = nullptr;
    return nums[0];
}

方法4：优先队列
时间复杂度：O(n logk)
空间复杂度：O(k)