面试题 02.07. 链表相交
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。
思路分析
题目的要求是求两个链表的交点,但是这里的交点是指指针相等,不是节点里面的值相同.
看如下两个链表，目前curA指向链表A的头结点，curB指向链表B的头结点,如何求得交点呢.
我们可以求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，如图：
此时我们就可以让CurA和CurB,从前往后遍历各自链表的节点,直到两者相等,此时对应的便是交点. 如果两个链表都遍历完还没有找到,则说明没有交点.
参考代码
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* curA = headA;
ListNode* curB = headB;
int lenA = 0,lenB = 0;
while(curA!=NULL){//求LenA长度
curA = curA->next;
lenA++;
}
while(curB!=NULL){//求LenB的长度
curB = curB->next;
lenB++;
}
if(lenB>lenA){//始终让A代表的是最长的链表
swap(curA,curB);
swap(lenA,lenB);
}
int gap = lenA-lenB;
while(gap--){
curA = curA->next;
}
while(curA!=NULL){
if(curA==curB){//注意:链表有交点指的是节点重复,而不是值重复.
return curA;
}
curA = curA->next;
curB = curB->next;
}
return NULL;
}
142. 环形链表 II
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 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
解释：链表中没有环。
思路分析
本题主要考察:
- 判断链表是否环
- 如果有环，如何找到这个环的入口
如何判断是否有环?:快慢指针
分别定义fast和slow指针,分别指向头结点,fast每次移动两个节点,slow每次移动一个节点,如果fast和slow指针在途中相遇,则说明这个链表有环.
这个过程就如同操场跑步一样,跑的快的人在一段时间后就会追上慢的人.
如果有环，如何找到这个环的入口 ? ? ?
从头结点出发一个指针index1，从相遇节点 也出发一个指针index2，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。
证明过程可以参考卡尔大佬的文章,讲的通俗易懂,嘿嘿嘿
参考代码
ListNode *detectCycle(ListNode *head) {
ListNode* fast,*slow;
fast = head;
slow = head;
while(fast!=NULL&&fast->next!=NULL){
slow = slow->next;//slow走一步
fast = fast->next->next;//fast走两步
if(slow==fast){//如果相遇
ListNode* index1 = fast;
ListNode* index2 = head;
while(index1!=index2){//此时如果相遇必定是入口节点
index1 = index1->next;
index2 = index2->next;
}
return index1;
}
}
return NULL;//如果没有环,则返回NULL
}
707. 设计链表
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能：
- get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
- addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
- addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
- addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
- deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
思路分析
盲猜面试出这个的可能性很大,很考查基础.
示例：
MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3
linkedList.get(1); //返回2
linkedList.deleteAtIndex(1); //现在链表是1-> 3
linkedList.get(1); //返回3
参考代码
#include<bits/stdc++.h>
using namespace std;
//很奇怪,按说是可以的...
class MyLinkedList {
public:
//定义链表
struct LinkedNode {
int val;
LinkedNode* next;
LinkedNode():val(0),next(NULL) {
};
LinkedNode(int x):val(x),next(NULL) {
};
LinkedNode(int x,LinkedNode* next):val(x),next(next) {
};
};
MyLinkedList() {
head = new LinkedNode();
size = 0;
}
//获取链表中 index 个节点的值。如果索引无效，则返回-1。
int get(int index) {
if(index<0 || index> size-1 ) {
return -1;
}
LinkedNode* cur = head->next;
while(index--) { //实际上是获得index+1个节点 ,因为index是从0开始的
cur = cur->next;
}
return cur->val;
}
// 在链表头部添加节点。
void addAtHead(int val) {
// ListNode *newNode = new ListNode(val,head->next);
// head->next = newNode;
head->next = new LinkedNode(val,head->next);
size++;
}
//链表尾部添加节点
void addAtTail(int val) {
LinkedNode* cur = head;
while(cur->next) {
cur = cur->next;
}
cur->next = new LinkedNode(val);
size++;
}
//在链表中的第index个节点之前添加值为val 的节点。
//如果index等于链表的长度，则该节点将附加到链表的末尾
//如果 index 大于链表长度，则不会插入节点。
//如果index小于0，则在头部插入节点。
void addAtIndex(int index, int val) {
if(index>size) { //如果 index 大于链表长度，则不会插入节点。
return;
}
if(index<0) { //如果index小于0，则在头部插入节点。
addAtHead(val);
}
if(index==size) { //如果index等于链表的长度，则该节点将附加到链表的末尾
addAtTail(val);
}
LinkedNode* cur = head;
while(index--) {
cur= cur->next;
}
cur->next = new LinkedNode(val,cur->next);
// ListNode *newNode = new ListNode(val);
// newNode->next = cur->next;
// cur->next = newNode;
size++;
}
//如果索引 index 有效，则删除链表中的第 index 个节点。
void deleteAtIndex(int index) {
if(index>=size||index<0) {
return;
}
LinkedNode* cur = head;
while(index--) {
cur = cur->next;
}
LinkedNode* temp = cur->next;
cur->next = cur->next->next;
delete temp;
size--;
}
void printLinkedList(){
LinkedNode* cur = head;
while(cur->next){
cout<<cur->next->val<<" ";
cur = cur->next;
}
cout<<endl;
}
private:
//全局变量
LinkedNode* head;
int size ;
};
int main() {
MyLinkedList* obj = new MyLinkedList();
int param_1 = obj->get(0);
cout<<param_1<<endl;
obj->addAtHead(1);
obj->printLinkedList();
obj->addAtTail(2);
obj->printLinkedList();
obj->addAtIndex(1,3);
obj->printLinkedList();
obj->deleteAtIndex(0);
obj->printLinkedList();
return 0;
}
备注:代码本身没啥问题,LeetCode关于这个题可能有点不严谨…
本文的相关题目以及思路参考自卡尔大佬的代码随想录