# 相交链表
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; | |
} |