c++刷题(9/100):链表

时间:2022-06-14 16:20:13

题目一: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