题目一：https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035?tpId=13&tqId=11156&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
题目描述
输入一个链表，从尾到头打印链表每个节点的值。
思路：之前看到书上两个链表相加然后（从tail开始）就发现这种从尾部开始的情况都可以用栈来实现，很容易理解，这题也一样
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
*/
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> list ;
stack<int> s ;
while(head!=NULL){
s.push(head->val) ;
head = head->next ;
}
while(!s.empty()){
list.push_back(s.top()) ;
s.pop() ;
}
return list ;
}
};
题目二：
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
思路：如果保留重复的节点就很简单，不保留的话，每次向后遍历删完节点之后还要把之前的第一个节点删了，需要判断一下，如果被删的是头节点，还要判断一下。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead)
{
if(pHead==NULL) {return NULL;}
set<int> s ;
ListNode* cur = pHead ;
ListNode* pre = pHead ;
ListNode* check ;
ListNode* checkpre ;
bool firstTodel ;
while(cur!=NULL){
int temp = cur->val ;
check = cur->next ;
checkpre = cur ;
firstTodel = false ;
while(check!=NULL){
if(check->val==temp){
checkpre->next = check->next ;
firstTodel = true ;
}else{
checkpre = check ;
}
check = check->next ;
}
if(firstTodel){
if(cur==pHead){
pHead = pHead->next ;
pre = pre->next ;
}else{
pre->next = cur->next ;
}
}else{
pre = cur ;
}
cur = cur->next ;
}
return pHead ;
}
};
题目三：
题目描述
一个链表中包含环，请找出该链表的环的入口结点。
思路：一开始想到set，后面觉得不行，因为可能会有两个一样的node，然后百度知道了双指针的方法。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
ListNode* fast ;
ListNode* slow ;
fast = pHead ;
slow = pHead ;
if(fast==NULL){
return NULL ;
}
while(fast!=NULL&&fast->next!=NULL){
fast = fast->next->next ;
slow = slow->next ;
if(fast==slow){
fast = pHead ;
while(fast!=slow){
fast = fast->next ;
slow = slow->next ;
}
return fast ;
}
}
return NULL ;
}
};
链表的总结：
有翻转性质的可以用栈，删除要记录前一个Node