各位朋友们大家好，今天是我leedcode刷题系列的第三篇，废话不多说，直接进入主题。
文章目录
- 分割链表
- 题目要求
- 用例输入
- 提示
- 做题思路
- c语言代码实现
- Java代码实现
- 相交链表
- 题目要求
- 用例输入
- 提示
- 做题思路
- c语言实现代码
- Java代码实现
分割链表
leetcode之分割链表（难度：中等）
题目要求
给你一个链表的头节点 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]
这是题目提供的接口
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* partition(struct ListNode* head, int x){
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
提示
提示：
链表中节点的数目在范围 [0, 200] 内
-100 <= Node.val <= 100
-200 <= x <= 200
做题思路
我们可以使用一个指针来遍历链表，遇到比x值小的数字就放在左侧，大于或等于的结点就放在右侧，最后再用指针将这两个部分连接起来，得出来的就是我们需要的结果。
定义四个结构体指针：bs和be分别指向小于x部分链表的头和尾，as和ae分别指向大于或等于x部分链表的头和尾。
持续这个动作，知道cur等于NULL。
然后我们这两部分用指针连接起来。并且将ae手动置为NULL，防止链表出现死循环。
我们在做完了之后我们还需要注意的是：当只有小于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;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
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;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
相交链表
leetcode之相交链表（难度：简单）
题目要求
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
用例输入
示例 1：
输入：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：
输入：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：
输入：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) {
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
提示
提示：
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;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
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;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
