面试题 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关于这个题可能有点不严谨…
