剑指offer计划12（双指针简单）---java

1.1、题目1

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

1.2、解法

递归判断结点大小进行赋值。

1.3、代码

/**
 * 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 l1!=null?l1:l2;
        if(l1.val>l2.val){
            l2.next=mergeTwoLists(l2.next,l1);
            return l2;
        }else{
            l1.next=mergeTwoLists(l1.next,l2);
            return l1;
        }
    }
}
           

2.1、题目2

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

2.2、解法

这题原本应该用双指针，但是哈希表不香吗？

2.3、代码

/**
 * 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) {
        HashSet<ListNode> h = new HashSet<ListNode>();
        while(headA!=null) {
            h.add(headA);
            headA=headA.next;

        }
        while(headB!=null) {
            if(h.contains(headB)) return headB;
            headB = headB.next;
        }
        return null;
    }
}