3月2日LeetCode刷题

# 相交链表

LeetCode：160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交 **：**
题目数据保证整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。


/* Definition for singly-linked list.
* 定义数据结构
*/
 public class ListNode {
     int val;
     ListNode next;
     ListNode(int x) {
         val = x;
         next = null;
     }
}

一开始我想到的是判重，可以用哈希表（Map 或者 Set）

// 使用HashMap 以cur.next节点为key，cur为value来找
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == headB){
            return headA;
        }
        Map<ListNode, ListNode> map = new HashMap<>();
        ListNode curA = new ListNode();
        ListNode curB = new ListNode();
        curA.next = headA;
        curB.next = headB;
        while(curA!=null || curB!=null) {
            if(curA!=null){
                if(map.containsKey(curA.next)){
                    return curA.next;
                }
                map.put(curA.next, curA);
                curA = curA.next;
            }
            if(curB!=null){
                if(map.containsKey(curB.next)){
                    return curB.next;
                }
                map.put(curB.next, curB);
                curB = curB.next;
            }
        }
        return null;
    }

// 用HashSet直接找
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == headB){
            return headA;
        }
        HashSet<ListNode> set = new HashSet<>();
        while(headA != null || headB != null) {
            if(headA != null) {
                if(set.contains(headA))
                    return headA;
                
                set.add(headA);
                headA = headA.next;
            }
            if(headB != null) {
                if(set.contains(headB))
                    return headB;
                set.add(headB);
                headB = headB.next;
            }
        }
        return null;
    }

可能条件有些冗余，但是可以在两个链表遍历完前找到相交节点。

看完题解后，时间复杂度 O (m+n)，空间 **O (1)** 的解法是：两链表相交后长度是一样的，那么我们不考虑相交后的节点，相交前两链表的节点数是不一样多的，这时候如果指针 headA 遍历完 A 链表去遍历 B 链表，同时 headB 遍历完 B 链表去遍历 A 链表，那么这两个指针在第二次到达相交节点时会相遇，即可得到第一个相交节点。

pA 指针遍历 A 链表，pB 指针遍历 B 链表
两指针同时遍历下一个
当 pA 到达 A 链表尾部，开始从头遍历 B 链表，当 pB 到达 B 链表尾部，开始从头遍历 B 链表
pA 与 pB 相遇，得到相交节点

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == headB){
            return headA;
        }
        ListNode pA = headA;
        ListNode pB = headB;
        while(pA != pB) {
            pA = pA == null? headB : pA.next;
            pB = pB == null? headA : pB.next;
        }
        return pA;
    }

# 字符串相加

LeetCode 415. 字符串相加

使用 StringBuilder 进行字符串拼接
双指针从最后一个数开始计算
count 记录进位

public String addStrings(String num1, String num2) {
        int len1 = num1.length() - 1;
        int len2 = num2.length() - 1;
        int count = 0;
        StringBuilder res = new StringBuilder();
        while(len1 >= 0 || len2 >= 0) {
            int a = len1 >= 0 ? num1.charAt(len1) - '0' : 0;
            int b = len2 >= 0 ? num2.charAt(len2) - '0' : 0;
            int sum = a + b + count;
            count = sum/10;
            res.append(sum%10);
            len1--;
            len2--;
        }
        if(count == 1) {
            res.append(1);
        }
        return res.reverse().toString();
    }

# 二分查找

704. 二分查找

public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            int num = nums[mid];
            if (num == target) {
                return mid;
            } else if (num > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

LeetCode 链表二分查找字符串相加

# 相交链表

# 字符串相加

# 二分查找

一些模板代码