leetcode刷题（3）

古城微笑少年丶 2023-09-25 23:08 15阅读 0赞

各位朋友们大家好，今天是我leedcode刷题系列的第三篇，废话不多说，直接进入主题。

#### 文章目录 ####

*  分割链表
 *   *  题目要求
     *  用例输入
     *  提示
     *  做题思路
     *  c语言代码实现
     *  Java代码实现
 *  相交链表
 *   *  题目要求
     *  用例输入
     *  提示
     *  做题思路
     *  c语言实现代码
     *  Java代码实现

## 分割链表 ##

[leetcode之分割链表（难度：中等）][leetcode]

### 题目要求 ###

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

你不需要 保留 每个分区中各节点的初始相对位置。

### 用例输入 ###

示例 1：  
![在这里插入图片描述][1793c64ba70e4bbfbe97b3ba51b9e495.png]  
输入：head = \[1,4,3,2,5,2\], x = 3  
输出：\[1,2,2,4,3,5\]

示例 2：  
输入：head = \[2,1\], x = 2  
输出：\[1,2\]

这是题目提供的接口

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

### 提示 ###

提示：

链表中节点的数目在范围 \[0, 200\] 内  
\-100 <= Node.val <= 100  
\-200 <= x <= 200

### 做题思路 ###

我们可以使用一个指针来遍历链表，遇到比x值小的数字就放在左侧，大于或等于的结点就放在右侧，最后再用指针将这两个部分连接起来，得出来的就是我们需要的结果。

![在这里插入图片描述][a7050618e8384fa3a4dedb6e3320590e.png]  
定义四个结构体指针：bs和be分别指向小于x部分链表的头和尾，as和ae分别指向大于或等于x部分链表的头和尾。  
![在这里插入图片描述][5a1325d9328c489f8a778e1f711efb20.png]  
![在这里插入图片描述][d9218f284f0348678076b535735fec1c.png]  
持续这个动作，知道cur等于NULL。  
![在这里插入图片描述][61a4673e45be4bdf8284a7bdebc8ec29.png]  
然后我们这两部分用指针连接起来。并且将ae手动置为NULL，防止链表出现死循环。  
![在这里插入图片描述][45f58312de2c45bb8f507f88d4c0ff0d.png]  
我们在做完了之后我们还需要注意的是：当只有小于x的值或者只有大于x的部分的时候我们上面的思路是不行的，我们需要做出判断，当bs为NULL时我们可以直接返回as，因为就算as也为NULL，返回的也是NULL。当as为NULL时，我们直接返回bs，不需要将ae置为NULL。

### c语言代码实现 ###

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    
    
    struct ListNode* partition(struct ListNode* head, int x){
        
    //定义四个结构体指针来管理小于和大于等于x两部分的链表
    	//小于x部分的头节点
        struct ListNode* bs = NULL;
        //小于x部分的尾节点
        struct ListNode* be = NULL;
        //大于x部分的头节点
        struct ListNode* as = NULL;
        //大于x部分的尾节点
        struct ListNode* ae = NULL;
        //cur用来遍历链表
        struct ListNode* cur = head;
        while(cur != NULL)
        {
        
            if(cur->val < x)
            {
        
            //当第一次出现小于x的节点的时候，bs和be都是这个节点
                if(bs == NULL)
                {
        
                    bs = cur;
                    be = cur;
                }
                else
                {
        
                    be->next = cur;
                    be = be->next;
                }
            }
            else
            {
        
            //第一次出现大于x的节点
                if(as == NULL)
                {
        
                    as = cur;
                    ae = cur;
                }
                else
                {
        
                    ae->next = cur;
                    ae = ae->next;
                }
            }
            cur = cur->next;
        }
        //判断是否有小于x的节点
        if(bs == NULL)
        {
        
            return as;
        }
        //连接两部分链表
        be->next = as;
        //判断是否有大于x的节点
        if(as != NULL)
        {
        
            ae->next = NULL;
        }
    
        return bs;
    }

![在这里插入图片描述][a1e4b7f3eb9947a79e740d4cd0ccdc53.png]

### Java代码实现 ###

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public ListNode partition(ListNode head, int x) {
        
        //我们的Java代码与c语言略有不同，
        //我们将bs和as作为哨兵位
            if(head == null) {
        
                return null;
            }
            ListNode bs = new ListNode(0);
            ListNode be = bs;
            ListNode as = new ListNode(0);
            ListNode ae = as;
            ListNode cur = head;
            while(cur != null) {
        
                if(cur.val < x) {
        
                    be.next = cur;
                    be = be.next;
                }else {
        
                    ae.next = cur;
                    ae = ae.next;
                }
                cur = cur.next;
            }
            if(bs.next == null) {
        
                return as.next;
            }
            be.next = as.next;
            if(as.next != null) {
        
                ae.next = null;
            }
    
            return bs.next;
        }
    }

![在这里插入图片描述][8d0adaee07a5474eb7f7ab80e5b90990.png]

## 相交链表 ##

[leetcode之相交链表（难度：简单）][leetcode 1]

### 题目要求 ###

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：  
![在这里插入图片描述][6565e8b9cee94e4096830891d9193869.png]  
题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

### 用例输入 ###

示例 1：  
![在这里插入图片描述][c2ba08ac749d42219d575976a262ccf4.png]

输入：intersectVal = 8, listA = \[4,1,8,4,5\], listB = \[5,6,1,8,4,5\], skipA = 2, skipB = 3

输出：Intersected at ‘8’

解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。  
从各自的表头开始算起，链表 A 为 \[4,1,8,4,5\]，链表 B 为 \[5,6,1,8,4,5\]。  
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。  
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例 2：  
![在这里插入图片描述][4e80a86c43224ff28d4cdeb5cd422bea.png]

输入：intersectVal = 2, listA = \[1,9,1,2,4\], listB = \[3,2,4\], skipA = 3, skipB = 1

输出：Intersected at ‘2’

解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。  
从各自的表头开始算起，链表 A 为 \[1,9,1,2,4\]，链表 B 为 \[3,2,4\]。  
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：  
![在这里插入图片描述][2549155c24b7443fbcdb1e2cb36b10a0.png]

输入：intersectVal = 0, listA = \[2,6,4\], listB = \[1,5\], skipA = 3, skipB = 2

输出：null

解释：从各自的表头开始算起，链表 A 为 \[2,6,4\]，链表 B 为 \[1,5\]。  
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。  
这两个链表不相交，因此返回 null 。

题目提供的接口

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    
    
    struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
        
    
    }

### 提示 ###

提示：

listA 中节点数目为 m  
listB 中节点数目为 n  
1 <= m, n <= 3 \* 104  
1 <= Node.val <= 105  
0 <= skipA <= m  
0 <= skipB <= n  
如果 listA 和 listB 没有交点，intersectVal 为 0  
如果 listA 和 listB 有交点，intersectVal == listA\[skipA\] == listB\[skipB\]

### 做题思路 ###

当这两个链表从后面剩余的节点的个数相同的地方开始走，他们会在相交节点相遇。但是因为两个链表的长度不一定是相同的，所以我们需要求出两个链表的长度的差值len，然后让长的链表先走len步，然后再一起走，当他们的地址相同时就说明到达了相交节点，我们就返回这个节点。

### c语言实现代码 ###

//我们将计算链表长度这个功能单独提出来，写成一个函数
    int listLength(struct ListNode* head)
    {
        
        struct ListNode* cur = head;
        int count = 0;
        while (cur != NULL)
        {
        
            count++;
            cur = cur->next;
        }
        return count;
    }
    
    struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
        
    //当其中一个链表为空就说明没有相交节点，我们直接返回
        if (headA == NULL || headB == NULL)
        {
        
            return NULL;
        }
        //我们将ll作为长度较长的链表的指针
        struct ListNode* ll = headA;
        //sl作为长度较短的链表的指针
        struct ListNode* sl = headB;
        int lenA = listLength(headA);
        int lenB = listLength(headB);
        int len = lenA - lenB;
        //如果len<0，我们就交换ll跟sl的指向
        if (len < 0)
        {
        
            ll = headB;
            sl = headA;
            len = -len;
        }
        for (int i = 0; i < len; i++)
        {
        
            ll = ll->next;
        }
        while (ll && sl)
        {
        
            if (ll == sl)
            {
        
                return ll;
            }
            ll = ll->next;
            sl = sl->next;
        }
        return NULL;
    }

![在这里插入图片描述][f5156aed48bc4b8399149e87331688aa.png]

### Java代码实现 ###

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    
     //链表长的就走差值步
     //pl永远指向较长的链表
     //p2永远指向较短的链表
    public class Solution {
        
        public int getLength(ListNode head) {
        
            int count = 0;
            ListNode cur = head;
            while(head != null) {
        
                head = head.next;
                count++;
            }
            return count;
        }
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        
            if(headA == null || headB == null) {
        
                return null;
            }
            ListNode pl = headA;
            ListNode ps = headB;
            int len1 = getLength(pl);
            int len2 = getLength(ps);
            int len = len1-len2;
            if(len < 0) {
        
                pl = headB;
                ps = headA;
                len = -len;
            }
            while(len != 0) {
        
                pl = pl.next;
                len--;
            }
            while(pl != ps) {
        
                pl = pl.next;
                ps = ps.next;
            }
    
            return pl;
        }
    }

![在这里插入图片描述][901ce0d47ef449319be52edb758f7bed.png]

[leetcode]: https://leetcode.cn/problems/partition-list-lcci/
[1793c64ba70e4bbfbe97b3ba51b9e495.png]: https://img-blog.csdnimg.cn/1793c64ba70e4bbfbe97b3ba51b9e495.png
[a7050618e8384fa3a4dedb6e3320590e.png]: https://img-blog.csdnimg.cn/a7050618e8384fa3a4dedb6e3320590e.png
[5a1325d9328c489f8a778e1f711efb20.png]: https://img-blog.csdnimg.cn/5a1325d9328c489f8a778e1f711efb20.png
[d9218f284f0348678076b535735fec1c.png]: https://img-blog.csdnimg.cn/d9218f284f0348678076b535735fec1c.png
[61a4673e45be4bdf8284a7bdebc8ec29.png]: https://img-blog.csdnimg.cn/61a4673e45be4bdf8284a7bdebc8ec29.png
[45f58312de2c45bb8f507f88d4c0ff0d.png]: https://img-blog.csdnimg.cn/45f58312de2c45bb8f507f88d4c0ff0d.png
[a1e4b7f3eb9947a79e740d4cd0ccdc53.png]: https://img-blog.csdnimg.cn/a1e4b7f3eb9947a79e740d4cd0ccdc53.png
[8d0adaee07a5474eb7f7ab80e5b90990.png]: https://img-blog.csdnimg.cn/8d0adaee07a5474eb7f7ab80e5b90990.png
[leetcode 1]: https://leetcode.cn/problems/intersection-of-two-linked-lists/
[6565e8b9cee94e4096830891d9193869.png]: https://img-blog.csdnimg.cn/6565e8b9cee94e4096830891d9193869.png
[c2ba08ac749d42219d575976a262ccf4.png]: https://img-blog.csdnimg.cn/c2ba08ac749d42219d575976a262ccf4.png
[4e80a86c43224ff28d4cdeb5cd422bea.png]: https://img-blog.csdnimg.cn/4e80a86c43224ff28d4cdeb5cd422bea.png
[2549155c24b7443fbcdb1e2cb36b10a0.png]: https://img-blog.csdnimg.cn/2549155c24b7443fbcdb1e2cb36b10a0.png
[f5156aed48bc4b8399149e87331688aa.png]: https://img-blog.csdnimg.cn/f5156aed48bc4b8399149e87331688aa.png
[901ce0d47ef449319be52edb758f7bed.png]: https://img-blog.csdnimg.cn/901ce0d47ef449319be52edb758f7bed.png