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 链表二分查找字符串相加

# 相交链表

# 字符串相加

# 二分查找

一些模板代码