剑指offer15——双指针(简单)

剑指 Offer 25. 合并两个排序的链表

难度 简单

输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1:

1
2
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4

限制:

1
0 <= 链表长度 <= 1000

注意:本题与主站 21 题相同:https://leetcode-cn.com/problems/merge-two-sorted-lists/

思路

开辟一个空节点用来返回,也可以在进入循环前进行一下判断,不开辟节点直接进循环

循环:将l1和l2中值较大的节点作为当前节点的下一节点

代码

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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1 == NULL)return l2;
if(l2 == NULL)return l1;
ListNode *head,*cur;
head = (ListNode*)malloc(sizeof(ListNode));
cur = head;
while( l1!=NULL && l2!=NULL )
{
if(l1->val <= l2->val)
{
cur->next = l1;
cur = cur->next;
l1 = l1->next;
}
else
{
cur->next = l2;
cur = cur->next;
l2 = l2->next;
}
}
if(l1 != NULL) cur->next = l1;
if(l2 != NULL) cur->next = l2;
return head->next;
}
};

剑指 Offer 52. 两个链表的第一个公共节点

难度 简单

输入两个链表,找出它们的第一个公共节点。

如下面的两个链表

img

在节点 c1 开始相交。

示例 1:

img

1
2
3
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出:Reference of the node with value = 8
输入解释:相交节点的值为 8 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。

示例 2:

img

1
2
3
输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出:Reference of the node with value = 2
输入解释:相交节点的值为 2 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [0,9,1,2,4],链表 B 为 [3,2,4]。在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。

示例 3:

img

1
2
3
4
输入: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

注意:

  • 如果两个链表没有交点,返回 null.
  • 在返回结果后,两个链表仍须保持原有的结构。
  • 可假定整个链表结构中没有循环。
  • 程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。
  • 本题与主站 160 题相同:https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

思路与题解

我们使用两个指针 node1,node2 分别指向两个链表 headA,headB 的头结点,然后同时分别逐结点遍历,当 node1 到达链表 headA 的末尾时,重新定位到链表 headB 的头结点;当 node2 到达链表 headB 的末尾时,重新定位到链表 headA 的头结点。

这样,当它们相遇时,所指向的结点就是第一个公共结点。

两个链表长度分别为L1+C、L2+C, C为公共部分的长度, 第一个人走了L1+C步后,回到第二个人起点走L2步;第2个人走了L2+C步后,回到第一个人起点走L1步。 当两个人走的步数都为L1+L2+C时就两个家伙就相爱了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *node1 = headA, *node2 = headB;

while (node1 != node2) {
node1 = node1 != NULL ? node1->next : headB;
node2 = node2 != NULL ? node2->next : headA;
}
return node1;
}
};