160.相交链表
题目
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
-
intersectVal- 相交的起始节点的值。如果不存在相交节点，这一值为0 -
listA- 第一个链表 -
listB- 第二个链表 -
skipA- 在listA中（从头节点开始）跳到交叉节点的节点数 -
skipB- 在listB中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。
思路
直接模拟，得到两个链表长度后让长的先走完两者差值然后再一起遍历，当两者相等时停下
代码如下：
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* targetA = headA;
ListNode* targetB = headB;
int lengthA = 0,lengthB = 0;
while(targetA || targetB){
if(targetA){
lengthA++;
targetA = targetA->next;
}
if(targetB){
lengthB++;
targetB = targetB->next;
}
}
if( lengthA > lengthB ){
int len = lengthA-lengthB;
while(len--){
headA = headA->next;
}
}
else{
int len = lengthB-lengthA;
while(len--){
headB = headB->next;
}
}
while(headA != headB && headA && headB){
headA = headA->next;
headB = headB->next;
}
if(headA == headB)return headA;
else return NULL;
}
};206.反转链表
题目
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2] 输出：[2,1]
示例 3：
输入：head = [] 输出：[]
思路
设两个指针，然后调换一次，更新一次，一直到末尾，（这个反转还好，后面有个题k组反转更难）
代码如下：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* first = NULL;
ListNode* second = head;
while(second){
ListNode* tmp = second->next;
second->next = first;
first = second;
second = tmp;
}
return first;
}
};234.回文链表
题目
给你一个单链表的头节点 head ，请你判断该链表是否为
回文链表
。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1] 输出：true
示例 2：
输入：head = [1,2] 输出：false
思路
遍历一次存到数组里面，然后用数组判断即可
代码如下：
class Solution {
public:
bool isPalindrome(ListNode* head) {
vector<int> a;
ListNode* tr = head;
while(tr){
a.emplace_back(tr->val);
tr = tr->next;
}
for(int i = 0;i < a.size()/2;i++){
if(a[i] != a[a.size()-1-i])return false;
}
return true;
}
};141.环形链表
题目
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：false 解释：链表中没有环。
思路
快慢指针，若是有环的话一定会相等的，不过有道题是环形链表II比这个难，那个需要判断环的入口，也是设快慢指针，设相等时两者走的路程为f和s，有f = 2*s同时f肯定比s多走了n圈环，假设环的长度为b，环之前长度
为a，a+nb一定到环入口，所以快慢指针相遇后，把其中一个移到开头，共同走a后一定会到环入口，也就是比这道题更难一点的了。
代码如下：
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head == NULL || head->next == NULL) return false;
ListNode* fast = head->next->next;
ListNode* slow = head->next;
while(fast != slow && fast && fast->next){
fast = fast->next->next;
slow = slow->next;
}
if(!fast || !fast->next) return false;
return true;
}
};142.环形链表II
题目
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：返回 null 解释：链表中没有环。
思路
上面一题提到了思路，代码如下：
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(head == NULL || head->next == NULL)return NULL;
ListNode* fast = head;
ListNode* slow = head;
while(1){
if(fast == NULL || fast->next == NULL)return NULL;
fast = fast->next->next;
slow = slow->next;
if(fast == slow) break;
}
slow = head;
while(fast != slow){
fast = fast->next;
slow = slow->next;
}
return fast;
}
};21.合并两个有序链表
题目
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = [] 输出：[]
示例 3：
输入：l1 = [], l2 = [0] 输出：[0]
思路
直接模拟，每次都取两者小的同时next，最后某个为空后直接接上另一个不为空的节点即可
代码如下：
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* boom=new ListNode();
ListNode* cur=boom;
while(list1&&list2){
if(list1->val<list2->val){
cur->next=list1;
list1=list1->next;
}
else{
cur->next=list2;
list2=list2->next;
}
cur=cur->next;
}
cur->next=list1?list1:list2;
return boom->next;
}
};2.两数相加
题目
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0] 输出：[0]
思路
维护一个进位值add，一开始l1+l2+add，更新add = (l1+l2+add)/10;和本位node = (l1+l2+add)%10;当其中一个为空后，假设是l1为空，则更新add = (l2+add)/10;和本位node = (l2+add)%10，最后若是add仍不为空，则补一个高位1接后面去（加法进位只可能是1）
代码如下：
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* ans = new ListNode();
ListNode* cur = ans;
int add = 0;
while(l1 && l2){
int res = (l1->val + l2->val + add)%10;
add = (l1->val + l2->val + add) / 10;
ListNode* node = new ListNode(res);
cur->next = node;
cur = cur->next;
l1 = l1->next;
l2 = l2->next;
}
if(l1){
while(l1){
int res = (l1->val+add)%10;
add = (l1->val+add)/10;
ListNode* node = new ListNode(res);
cur->next = node;
cur = cur->next;
l1 = l1->next;
}
}
else{
while(l2){
int res = (l2->val+add)%10;
add = (l2->val+add)/10;
ListNode* node = new ListNode(res);
cur->next = node;
cur = cur->next;
l2 = l2->next;
}
}
if(add != 0){
ListNode* node = new ListNode(add);
cur->next = node;
}
return ans->next;
}
};
