1.逆置(1.藉助頭結點2.不借助頭結點）
void Reverse_List1(Node* plist)
{
//1.準備工作(申請兩個指針p和q，分別指向第一個有效節點和第二個有效節點)
Node* p = plist->next;//第一個節點
Node* q = NULL;//Node*p=p->next;
//2.斷開頭結點
plist->next = NULL;
while (p != NULL)
{
q = p->next;
p->next = plist->next;
plist->next = p;
p = q;
}
}struct ListNode* reverseList(struct ListNode* head) {
if(head==NULL)return NULL;
struct ListNode*p1=NULL;
struct ListNode*p2=head;
struct ListNode*p3=head->next;
while(p2!=NULL)
{
p2->next=p1;
p1=p2;
p2=p3;
if(p3!=NULL)
{
p3=p3->next;
}
}
return p1;
}2.判斷兩個單鏈表是否存在交點，如果存交點，則找到相交的第一個點
2.1 如果面試官沒有讓找相交點，只是問你是否相交(可以用一個非常簡單的方法)
Node* Intersect(Node* plist1, Node* plist2)
{
Node* p = plist1;
Node* q = plist2;
for (; p != NULL; p = p->next);
for (; q != NULL; q = q->next);
if (q != p)
return NULL;
}2.2如果面試官既要判斷是否相交，還要問你相交點在哪(另外一種解題思路)
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
if(headA == NULL || headB == NULL) return NULL; // 修改：檢查空鏈表而不是next
int i=0,j=0;
int sum=0;
struct ListNode *p1=headA;
struct ListNode *p2=headB;
while(p1!=NULL)
{
p1=p1->next;
i++;
}
while(p2!=NULL)
{
p2=p2->next;
j++;
}
p1 = headA;
p2 = headB;
if(i>j)sum=i-j;
else if(i<j)sum=j-i;
if(i>j)
{
while(sum>0)
{
p1=p1->next;
sum--;
}
}
if(i<j){
while(sum>0)
{
p2=p2->next;
sum--;
}
}
while(p1 != NULL && p2 != NULL)
{
if(p1==p2)return p1;
else{
p1=p1->next;
p2=p2->next;
}
}
return NULL;
}3.任意刪除一個節點(要求時間複雜度為0(1)，給的這個節點的地址不能是尾結點)
bool Delete(Node* p)
{
assert(p != NULL);
if (p->next == NULL)return false;
Node* q = p->next;
p->data = q->data;
Node* r = q->next;
p->next = r;
free(r);
r = NULL;
return true;
}4.1.判斷一個單鏈表是否存在環 2如果確存在環，則找到入環點
bool hasCycle(struct ListNode *head) {
if(head==NULL)return false;
if(head->next==NULL)return false;
struct ListNode *p=head;
struct ListNode *q=head->next;
while(q != NULL && q->next != NULL)
{
if(q==p)
{
return true;
}
else
{
p=p->next;
q=q->next->next;
}
}
return false;
}Node* Find_FristCirCleNode(Node* plist)
{
if (Is_Empty(plist))
return NULL;
Node* slow = plist;
Node* quick = plist;
slow = slow->next;
quick = quick->next->next;
while (quick != NULL && quick != slow)
{
slow = slow->next;
//quick = quick->next->next; //bug
quick = quick->next;
if (quick != NULL)
quick = quick->next;
}
if (quick == NULL)
{
return NULL;
}
//怎麼找入環點：讓兩個指針，1個從初始位置出發，1個從快慢指針相遇點出發，
保持同樣的速度，當這兩個指針相遇的時候，相遇節點就是找的第一個入環點
Node* p = plist;
Node* q = quick;//slow
while (p!=q)
{
p = p->next;
q = q->next;
}
return p;//q
}5.確定一個單鏈表是否迴文12321(ES)123321(YES)123(YES)
5.1藉助棧來實現
5.2除2隊後面的鏈表進行逆置
#include <stack>
bool Is_Palindrome(Node* plist)
{
std::stack<Node*> st;
int len = Get_Length(plist);
Node* p = plist->next;
for (int i = 0; i < len / 2; i++)
{
st.push(p);
p = p->next;
}
if (len % 2 == 1)
p = p->next;
while (!st.empty() && p != NULL)
{
if (st.top()->data != p->data)
{
return false;
}
else
{
p = p->next;
st.pop();
}
}
return true;
}struct ListNode* reverseList(struct ListNode* head) {
if(head==NULL)return NULL;
struct ListNode*p1=NULL;
struct ListNode*p2=head;
struct ListNode*p3=head->next;
while(p2!=NULL)
{
p2->next=p1;
p1=p2;
p2=p3;
if(p3!=NULL)
{
p3=p3->next;
}
}
return p1;
}
bool isPalindrome(struct ListNode* head){
if(head==NULL)return false;
if(head->next==NULL)return true;
int i=0;
struct ListNode*p=head;
while(p!=NULL)
{
p=p->next;
i++;
}
p=head;
for(int j=0;j<i/2;j++)
{
p=p->next;
}
if(i%2==1)
{
p=p->next;
}
struct ListNode* r=reverseList(p);
struct ListNode*q=head;
while(r!=NULL)
{
if(q->val!=r->val)return false;
else
{
r=r->next;
q=q->next;
}
}
return true;
}6.找到單鏈表倒數第K個節點
int kthToLast(struct ListNode* head, int k) {
struct ListNode*p=head;
struct ListNode*q=head;
for(;k!=0;k--)
{
q=q->next;
}
while(q!=NULL)
{
p=p->next;
q=q->next;
}
return p->val;
}本文章為轉載內容，我們尊重原作者對文章享有的著作權。如有內容錯誤或侵權問題，歡迎原作者聯繫我們進行內容更正或刪除文章。
