[剑指offer] 链表
题目描述
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
解题思路：
快慢指针检测链表是否有环的原理很简单，每次 快指针走2步， 慢指针走一步， 快指针必定在环内某一节点追上慢指针。
本题还需要找出环入口，
image.png
我们假设
- 起点 到 环入口长度为X
- 环长度为 K
- 慢指针 进入环内又走了Y
当 快慢指针相遇时，
慢指针走了： X+ Y 步
快指针比慢指针多跑一个环的长度为： X+ Y+ K 步
又知 快指针 为慢指针步数的2倍
所以有 X+Y + K= 2(X+Y)
K = X+Y --> X = K-Y
我们发现慢指针正好走了环的长度 ， 并且再走 X 步 就可以走到环入口。
然而 我们并不知道X 步 有多长， 但我们发现如果让快指针重新从 起点出发，每次走一步， 那么快指针正好 走X步后 与 慢指针相遇于 环入口。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
if (!pHead)
return NULL;
//快慢指针
ListNode* low = pHead;
ListNode* fast = pHead;
//保证快指针 不出界
while(fast->next && fast->next->next){
// 慢走一步， 快走2步
low = low->next;
fast = fast->next->next;
//快慢指针相遇
if(low == fast)
{
fast = pHead;
//快指针重新从头出发，每次一布
// 会与 慢指针相遇 与 环入口
while(low!= fast){
fast=fast->next;
low=low->next;
}
return fast;
}
}
return NULL;
}
};
题目描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
解题思路：
这题我用了递归的写法。
deleteDuplication(node) 函数的作用 就是 返回 node 节点往后的 第一个 不重复节点（有可能不是node, 比如 node 本身就是重复节点）
设 当前节点为A， A 的下一个节点为B.
如果A 不等于 B , 那么A 一定是一个不重复的点（因为我们保证了A点和前节点不一样）， 令 A 指向 deleteDuplication（B）， 返回A点。
反之， A 等于 B， 那么A，B 都是重复点， 那么我们next(B) 直到 找到一个新的B 不等于A（这里有可能没有新B， 说明A往后 都是 同一个数， 直接返回NULL）。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead)
{
//该点为空， 或者最后一个点
if(!pHead || (pHead && !pHead->next))
return pHead;
ListNode* a = pHead;
ListNode* b = pHead->next;
if (a->val != b->val){
a->next = deleteDuplication(b);
return a;
}else{
//重复点
while(b->val == a->val){
if(b->next)
b = b->next;
else
return NULL;
}
return deleteDuplication(b);
}
}
};
题目描述
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
方法一： 借助stack 先进后出， 遍历一边链表写入stack, 再把stack的元素全部 pop 到vector 中。
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
*/
#include <stack>
using namespace std;
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> res;
stack<int> temp;
while(head){
temp.push(head->val);
head = head->next;
}
while(!temp.empty()){
res.push_back(temp.top());
temp.pop();
}
return res;
}
};
方法二： 递归
先展开， 后打印。
所以程序会一直递归到最后一个节点，在把最后一个节点加入vector中， 接着回溯，一次往前加节点。
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
*/
class Solution {
private:
vector<int> res;
public:
vector<int> printListFromTailToHead(ListNode* head) {
if(head){
printListFromTailToHead(head->next);
res.push_back(head->val);
}
return res;
}
};
