1. 首页
  2. 文章资讯

leetcode算法刷题记录---6

20 阅读 0 评论

合并K个升序链表（leetcode23）

C++

#include <vector>
using namespace std;

// 合并K个升序链表
struct ListNode {
    int val;
    ListNode *next;

    ListNode() : val(0), next(nullptr) {}

    ListNode(int x) : val(x), next(nullptr) {}

    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {

        if(lists.empty()) return nullptr;
        ListNode * res = lists[0];
        for(int i=1; i<lists.size();i++){
            res = mergeTwoLists(res,lists[i]);
        }
        return res;
    }

    ListNode *mergeTwoLists(ListNode *linklist1, ListNode *linklist2) {
        if (linklist1 == nullptr) return linklist2;
        if (linklist2 == nullptr) return linklist1;
        // 新建虚拟头节点
        ListNode *dummy = new ListNode(0, nullptr);
        ListNode *end = dummy;
        while (linklist1 && linklist2) {
            ListNode *tmp;
            if (linklist1->val < linklist2->val) {
                tmp = linklist1;
                linklist1 = linklist1->next;

            } else {
                tmp = linklist2;
                linklist2 = linklist2->next;

            }
            tmp->next = nullptr;
            end->next = tmp;
            end = tmp;
        }

        if(linklist1) end->next = linklist1;
        if(linklist2) end->next = linklist2;
        end = dummy->next;
        delete dummy;
        return end;
    }
};

Python

from typing import Optional,List
# 合并K个升序链表
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None
        res = lists[0]
        # 两两合并
        for i in lists[1:]:
            res = self.mergeTwoLists(res,i)
        return res

    def mergeTwoLists(self,linklist1: Optional[ListNode],linklist2: Optional[ListNode])->Optional[ListNode]:

        if not linklist1:
            return linklist2
        if not linklist2:
            return linklist1
        # 新建虚拟头节点
        dummy = ListNode(0,None)
        q = dummy
        while linklist1 and linklist2:
            if linklist1.val<linklist2.val:
                p = linklist1
                linklist1 = linklist1.next
            else:
                p = linklist2
                linklist2 = linklist2.next
            p.next = None
            q.next = p
            q = p
        if linklist1:
            q.next = linklist1
        if linklist2:
            q.next = linklist2
        return dummy.next
if __name__ == '__main__':
    test = [[1, 4, 5], [1, 3, 4], [2, 6]]
    a = ListNode(1,ListNode(4,ListNode(5,None)))
    b = ListNode(1,ListNode(3,ListNode(4,None)))
    c = ListNode(2,ListNode(6,None))
    s = Solution()
    res = s.mergeKLists([a,b,c])
    while res:
        print(res.val)
        res = res.next

重排链表（leetcode143）

C++

from typing import Optional
# 重排链表
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def reorderList(self, head: Optional[ListNode]):
        """
        Do not return anything, modify head in-place instead.
        """
        mid = self.findMidNode(head)
        l2 = mid.next
        mid.next = None
        l2 = self.reverseLinkList(l2)
        head = self.mergeLinkList(head,l2)
        return head

    def findMidNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None
        # 定义快慢指针
        fast = head
        slow = head
        # # 快指针每次走两步，需要next存在才能
        # while fast and fast.next:
        #     fast = fast.next.next
        #     slow = slow.next
        # # 当节点为偶数时，slow指向中间右侧节点，fast指向尾节点后的空位置 ；当节点为奇数时，slow指向中间节点，fast指向尾节点
        # return slow

        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
        # 当节点为偶数时，slow指向中间左侧节点，fast指向尾节点 ；当节点为奇数时，slow指向中间节点，fast指向尾节点前第两个节点
        return slow
    def reverseLinkList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None
        # 当前节点
        cur = head.next
        head.next = None
        while cur:
            later = cur.next
            cur.next = head
            head = cur
            cur = later
        return head

    def mergeLinkList(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        head = l1
        while l1 and l2:
            p = l1.next
            q = l2.next
            l1.next = l2
            l2.next = p
            l1 = p
            l2 = q
        return head

if __name__ == '__main__':
    nums = [1, 2, 3, 4]
    head = ListNode(1,ListNode(2,ListNode(3,ListNode(4))))
    s = Solution()
    res = s.reorderList(head)
    while res:
        print(res.val)
        res = res.next

Python

from typing import Optional
# 重排链表
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def reorderList(self, head: Optional[ListNode]):
        """
        Do not return anything, modify head in-place instead.
        """
        mid = self.findMidNode(head)
        l2 = mid.next
        mid.next = None
        l2 = self.reverseLinkList(l2)
        head = self.mergeLinkList(head,l2)
        return head

    def findMidNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None
        # 定义快慢指针
        fast = head
        slow = head
        # # 快指针每次走两步，需要next存在才能
        # while fast and fast.next:
        #     fast = fast.next.next
        #     slow = slow.next
        # # 当节点为偶数时，slow指向中间右侧节点，fast指向尾节点后的空位置 ；当节点为奇数时，slow指向中间节点，fast指向尾节点
        # return slow

        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
        # 当节点为偶数时，slow指向中间左侧节点，fast指向尾节点 ；当节点为奇数时，slow指向中间节点，fast指向尾节点前第两个节点
        return slow
    def reverseLinkList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None
        # 当前节点
        cur = head.next
        head.next = None
        while cur:
            later = cur.next
            cur.next = head
            head = cur
            cur = later
        return head

    def mergeLinkList(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        head = l1
        while l1 and l2:
            p = l1.next
            q = l2.next
            l1.next = l2
            l2.next = p
            l1 = p
            l2 = q
        return head

if __name__ == '__main__':
    nums = [1, 2, 3, 4]
    head = ListNode(1,ListNode(2,ListNode(3,ListNode(4))))
    s = Solution()
    res = s.reorderList(head)
    while res:
        print(res.val)
        res = res.next

删除链表的倒数第N个结点（leetcode19）

C++

// 删除链表的倒数第N个结点
struct ListNode {
    int val;
    ListNode *next;

    ListNode() : val(0), next(nullptr) {}

    ListNode(int x) : val(x), next(nullptr) {}

    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        if (head->next == nullptr) return nullptr;
        // 定义前后指针
        ListNode *front = head;
        ListNode *behind = head;
        // 前指针先走n步
        for(int i=0;i<n;i++){
            front = front->next;
        }
        // 如果front成了空指针，那么要删除的为头节点
        if(front== nullptr) return head->next;
        // 同步移动前后指针，前指针最多走到最尾节点，后指针便走到删除节点的前一个节点
        while(front && front->next){
            front = front->next;
            behind = behind->next;
        }
        // 删除节点
        behind->next = behind->next->next;
        return head;
    }
};

Python

from typing import Optional
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # 仅有头节点，那么删除头节点
        if not head.next:
            return None
        # 定义前后指针
        front = head
        bebind = head
        # front先走n步
        for _ in range(n):
            front = front.next

        # 如果走到了结尾后,那么删除的是头节点
        if not front:
            return head.next

        # front最多走到链表结尾
        while front and front.next:
            front = front.next
            bebind = bebind.next
        bebind.next = bebind.next.next
        return head

if __name__ == '__main__':
    head = ListNode(1,ListNode(2))
    n = 2
    s = Solution()
    res = s.removeNthFromEnd(head,n)
    while res:
        print(res.val)
        res = res.next

合并区间（leetcode56）

C++

#include <vector>
#include <algorithm>

using namespace std;
// 合并区间
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        // 仅有一个区间
        if(intervals.size()==1) return intervals;
        // 定义结果数组
        vector<vector<int>> res;
        // 对intervals进行区间左边界排序
        sort(intervals.begin(),intervals.end());
        // 定义初始比较区间边界
        int start = intervals[0][0];
        int end = intervals[0][1];
        for(int i=1;i<intervals.size();i++){
            if(intervals[i][0]>end){
                res.push_back(vector<int>{start,end});
                start = intervals[i][0];
                end = intervals[i][1];
            } else{
                end = max(end,intervals[i][1]);
            }
        }
        res.push_back(vector<int>{start,end});
        return res;
    }
};

Python

from typing import List
# 合并区间
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if len(intervals)==1:
            return intervals
        # 定义结果
        res = []
        # 先对区间按左边界进行排序
        intervals.sort()
        # 定义初始比较
        start = intervals[0][0]
        end = intervals[0][1]
        # 遍历区间
        for i in intervals[1:]:
            # 无交集
            if i[0]>end:
                res.append([start,end])
                start = i[0]
                end = i[1]
            else:
                end = max(end,i[1])
        res.append([start,end])
        return res

if __name__ == '__main__':
    # intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
    intervals = [[1, 4], [0, 4]]
    s = Solution()
    res = s.merge(intervals)
    print(res)

删除排序链表中的重复元素||（leetcode82）

C++

// 删除排序链表中的重复元素||
struct ListNode {
    int val;
    ListNode *next;

    ListNode() : val(0), next(nullptr) {}

    ListNode(int x) : val(x), next(nullptr) {}

    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        if (head == nullptr) return nullptr;
        if (head->next == nullptr) return head;
        // 定义虚拟头节点
        ListNode *dummy = new ListNode(0, head);
        // 遍历链表的指针
        ListNode *start = dummy;
        // 判断是否是重复元素的指针
        ListNode *end;
        while (start->next) {
            end = start->next;
            while (end->next && end->next->val==end->val) end = end->next;
            if(end==start->next){
                start = start->next;
            } else{
                start->next = end->next;
            }
        }
        head = dummy->next;
        delete dummy;
        return head;
    }
};

Python

from typing import Optional
# 删除排序链表中的重复元素||
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None
        if not head.next:
            return head
        # 定义虚拟头节点
        dummy = ListNode(0,head)

        # 定义start，end指针。start指向已经去除重复节点的末尾，end用于判断后续是否有重复节点
        start = dummy
        while start.next:
            end = start.next
            while end.next and end.next.val == end.val:
                end = end.next
            if end==start.next:
                start = start.next
            else:
                start.next = end.next
        return dummy.next

本站资源均来自互联网，仅供研究学习，禁止违法使用和商用，产生法律纠纷本站概不负责！如果侵犯了您的权益请与我们联系！

转载请注明出处： 免费源码网-免费的源码资源网站 » leetcode算法刷题记录---6

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

 发表
评论 返回
顶部