【Leetcode -86.分隔链表 -92.反转链表Ⅱ】

简介: 【Leetcode -86.分隔链表 -92.反转链表Ⅱ】

Leetcode -86.分隔链表

题目:给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

示例 1:

输入:head = [1, 4, 3, 2, 5, 2], x = 3

输出:[1, 2, 2, 4, 3, 5]

示例 2:

输入:head = [2, 1], x = 2

输出:[1, 2]

我们的思路是,遍历链表的每个元素,如果比x小则拿下来放到一个small的结构体指针中;否则,放到一个large的指针中;最后,判断small是否为空,如果为空,则说明链表中的元素全都是比x大或等于x;否则,链表中的元素有比x大或等于,也有比x小的,这时候将small的尾部接到large上即可;

struct ListNode* partition(struct ListNode* head, int x)
    {
        //small放比x小的值
        //large放大于等于x的值
        //smalltail和largetail分别是它们的尾
        struct ListNode* large = NULL, * small = NULL;
        struct ListNode* largetail = NULL, * smalltail = NULL;
        //从头开始遍历,到空结束
        while (head)
        {
            //head的val比x小,放到small
            if (head->val < x)
            {
                //当small为空,即没有值的时候,small和smalltail都更新为当前的head
                //head迭代往后走,尾的next置空
                if (small == NULL)
                {
                    small = smalltail = head;
                    head = head->next;
                    smalltail->next = NULL;
                }
                //否则,更新尾并迭代head即可
                else
                {
                    smalltail->next = head;
                    head = head->next;
                    smalltail = smalltail->next;
                    smalltail->next = NULL;
                }
            }
            //当head的val比x大或等于x,与上面类似
            else
            {
                if (large == NULL)
                {
                    large = largetail = head;
                    head = head->next;
                    largetail->next = NULL;
                }
                else
                {
                    largetail->next = head;
                    head = head->next;
                    largetail = largetail->next;
                    largetail->next = NULL;
                }
            }
        }
        //如果链表中的值有大有小,即small这个链表不为空,就将small尾部的next接到large,然后再返回small
        if (small)
            smalltail->next = large;
        //这种情况则是链表中的值全都大于或等于x,直接返回large即可
        else
            return large;
        return small;
    }

Leetcode -92.反转链表Ⅱ

题目:给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。

请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。

示例 1:

输入:head = [1, 2, 3, 4, 5], left = 2, right = 4

输出:[1, 4, 3, 2, 5]

示例 2:

输入:head = [5], left = 1, right = 1

输出:[5]

我们的思路是,使用leftcur和rightcur指针走到链表中left位置和right位置,反转left位置到right位置即可;当left为1,即在头节点的位置时,最终只需要返回反转后的链表;当left不在头节点的位置,我们用一个指针cur记录leftcur的前一个位置,我们只需要将cur->next 接到反转后的链表,并返回头节点即可;

当left = 1,right = 3:

反转后整理的链表,返回prev即可,即返回反转后的链表;

当left不为1,left = 2,right = 3:

在函数中反转后的链表如下两个图,所以需要将原链表中cur->next接到反转后的链表中,再返回head;

代码以及注释:

struct ListNode* Reverse(struct ListNode* prev, struct ListNode* dest)
    {
        struct ListNode* curr = prev->next;
        prev->next = dest->next;
        while (prev != dest)
        {
            struct ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
    struct ListNode* reverseBetween(struct ListNode* head, int left, int right)
    {
        //当左下标和右下标相同,不需要反转,返回head
        if (left == right)
            return head;
        struct ListNode* cur = head;
        struct ListNode* leftcur = head, * rightcur = head;
        //leftcur走到链表中left的位置
        while (--left)
        {
            leftcur = leftcur->next;
        }
        //rightcur走到链表中right的位置
        while (--right)
        {
            rightcur = rightcur->next;
        }
        //cur从头遍历,当cur等于leftcur或者cur->next等于leftcur时停下
        while (cur != leftcur && cur->next != leftcur)
        {
            cur = cur->next;
        }
        //cur->next等于leftcur,反转leftcur到rightcur长度的链表
        //并且将cur的next接到反转后的链表去
        //返回头节点
        if (cur != leftcur)
        {
            cur->next = Reverse(leftcur, rightcur);
            return head;
        }
        //cur等于leftcur,即cur = leftcur = head,
        //就反转leftcur到rightcur长度的链表,返回反转后的链表即可
        else
        {
            return Reverse(leftcur, rightcur);
        }
    }
目录
相关文章
|
5月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
56 1
|
5月前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
132 0
|
5月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
52 0
LeetCode第二十四题(两两交换链表中的节点)
|
5月前
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
78 0
Leetcode第21题(合并两个有序链表)
|
5月前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
61 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
5月前
【LeetCode 10】142. 环形链表 II
【LeetCode 10】142. 环形链表 II
39 0
|
5月前
【LeetCode 09】19 删除链表的倒数第 N 个结点
【LeetCode 09】19 删除链表的倒数第 N 个结点
29 0
|
9月前
|
算法
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
|
9月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
9月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表