「剑指Offer」Day12：双指针（简单）
剑指 Offer 25. 合并两个排序的链表
题目描述
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
方法一：双指针
遍历两个链表，比较当前节点，小的就接到新链表上，并将对应的指针移到下一位，继续比较
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null && l2 == null){
return null;
}
ListNode l3 = new ListNode(-1);
ListNode pre = l3;
while(l1 != null && l2 != null){
if(l1.val < l2.val){ //小的先连接到新链表上，并移动
l3.next = l1;
l1 = l1.next;
}else{
l3.next = l2;
l2 = l2.next;
}
l3 = l3.next;
}
l3.next = l1 != null ? l1 : l2; //剩下不为空的链表直接接到新链表后面
return pre.next;
}
}
方法二：递归
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) { //递归
if(l1 == null){
return l2;
}else if(l2 == null){
return l1;
}else if(l1.val < l2.val){
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}else{
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
剑指 Offer 52. 两个链表的第一个公共节点
题目描述
输入两个链表，找出它们的第一个公共节点。输入：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 个节点。
思路
分别对链表A和B进行遍历，链表A走完接着走B，B走完走A，使得它们走的长度相同，这时遍历到的相同节点，即为相交点
实现代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null){
return null;
}
ListNode h1 = headA;
ListNode h2 = headB;
while(h1 != h2){
h1 = h1 == null ? headB : h1.next;
h2 = h2 == null ? headA : h2.next;
}
return h1;
}
}
查看22道真题和解析