链表

作者: juriau | 来源:发表于2020-02-24 15:48 被阅读0次

一、目录

  • 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)

相关文章

  • 链表基础

    链表基础 链表长度 链表为空 链表结构 链表增加

  • 双向链表&双向循环链表

    链表分为:单链表、单向循环链表、双向链表、双向循环链表本节主要说明:双向链表、双向循环链表 定义结点 一、双向链表...

  • 算法与数据结构:链表

    链表 链表还分为单向链表和双向链表, 但是这篇文章只说单向链表 , 下次再讲双向链表 . 链表和数组的区别 ? 链...

  • 链表

    链表 单链表反转链表中环的检测两个有序链表合并删除链表倒数第n个节点求链表的元素总个数 一.单向链表 链表共有特征...

  • 五、双向链表

    双向链表 此前介绍的链表,也叫做单向链表使用双向链表可以提升链表的综合性能 修改之前的单链表的源码: 双向链表 –...

  • 链表

    内容 链表数据结构 向链表添加元素 从链表移除元素 使用 LinkedList 表 双向链表 循环链表 链表数据结...

  • 数据与算法结构

    线性表 顺序表 链表(物理上离散,逻辑上连续) 链表的类别 单链表 循环链表 双链表 链表的操作 顺序表与链表的比...

  • 数据结构——链表

    本文所讲的链表是单链表,链表采用无头链表 科普下:一般链表可以分为有头节点的链表与无头节点的链表 有头节点的链表:...

  • 链表

    文章结构 链表的定义 链表的插入和删除操作 链表的特性 常见的链表结构 自定义链表 链表的经典操作 使用链表实现L...

  • Algorithm小白入门 -- 单链表

    单链表递归反转链表k个一组反转链表回文链表 1. 递归反转链表 单链表节点的结构如下: 1.1 递归反转整个单链表...

网友评论

      本文标题:链表

      本文链接:https://www.haomeiwen.com/subject/epivqhtx.html