数据结构之链表算法题

一：移除链表元素

我们很容易就可以想到一个解决方案：再创建一个链表，把不是val的结点拿过来尾插。

这样确实可以但是，我们每次尾插都需要遍历一遍整个链表，这样时间复杂度就变成了O(n^2)，

因此我们不妨设置一个tail尾结点来指向它的尾。

画图分析：

这里面还有一个潜在的问题就是，假如最后一个节点的数值==val怎么办，想一想。

完整代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {ListNode* newhead;ListNode* newtail;ListNode* pcur = head;newhead=newtail=NULL;while(pcur){if(pcur->val!=val){if(newhead==NULL){newhead=newtail=pcur;}else{newtail->next=pcur;newtail=pcur;}}pcur=pcur->next;}if(newtail!=NULL&&newtail->next!=NULL){newtail->next=NULL;}return newhead;
}

二：反转链表

这一题有两种解法：

解法一：

直接反转指向，比如原来二指向三，现在让三指向2.

画图分析：

经过分析我们写出了这样的代码：

struct ListNode* reverseList(struct ListNode* head) {

    struct ListNode* pprev = NULL;

    struct ListNode* pcur = head;

    struct ListNode* pnext = head->next;

    while(pcur)

    {

        pcur->next=pprev;

        pprev=pcur;

        pcur=pnext;

        pnext=pnext->next;

    }

    return pprev;

}

放在力扣上提交

遇到错误不要慌张，我们看一下提示信息，可以发现，原来是对NULL解引用了，所以在17行那要加上判断，那么说到这了万一这个链表原来就是空呢？因此在一开始也要对这种情况处理。

完整代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* pprev = NULL;struct ListNode* pcur = head;struct ListNode* pnext;if(head){pnext = head->next;}while(pcur){pcur->next=pprev;pprev=pcur;pcur=pnext;if(pnext){pnext=pnext->next;}}return pprev;
}

解法二：

取原链表中元素，头插到新链表的newhead中。

画图分析：

完整代码：

struct ListNode* reverseList(struct ListNode* head) {struct ListNode* pcur = head;struct ListNode* newhead = NULL;struct ListNode* pnext;if(head){pnext=head->next;}while(pcur){pcur->next = newhead;newhead = pcur;pcur = pnext;if(pnext){pnext = pnext->next;}}return newhead;
}

三：链表的倒数k个结点

我们确实可以先遍历一遍拿到链表长度，然后就可以找到倒数k个结点了。但是如果只能这么做就没有拿出来的必要了qwq。

快慢指针法：两个指针先让一个走k，然后一起走，等到k指向空（具体看下面画图分析）结束。

画图分析：

完整代码：

struct ListNode* FindKthToTail(struct ListNode* pHead, int k ) {struct ListNode* slow;struct ListNode* fast;slow=fast=pHead;while(k--){if(fast){fast=fast->next;}else {return NULL;}}while(fast){slow=slow->next;fast=fast->next;}return slow;
}

四：链表的中间结点

这题同样也是快慢指针法,大体思路是让fast走两步，slow走一步，但是直觉告诉我们结点数的奇偶性会影响结束条件。

画图分析：

完整代码：

struct ListNode* middleNode(struct ListNode* head) {struct ListNode* slow;struct ListNode* fast;fast=slow=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}return slow;
}

五：合并两个有序链表

思路：依次比较链表中的结点，然后插入小的结点

画图分析：

完整代码：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {struct ListNode* newhead;struct ListNode* newtail;newhead=newtail=NULL;struct ListNode* pcur1=list1;struct ListNode* pcur2=list2;if(pcur1==NULL)return pcur2;if(pcur2==NULL)return pcur1;while(pcur1&&pcur2){if(pcur1->val<pcur2->val){if(newhead==NULL){   newhead=newtail=pcur1;}else{newtail->next=pcur1;newtail=pcur1;}pcur1=pcur1->next;}else{if(newhead==NULL){   newhead=newtail=pcur2;}else{newtail->next=pcur2;newtail=pcur2;}pcur2=pcur2->next;}}if(pcur1!=NULL){newtail->next=pcur1;}if(pcur2!=NULL){newtail->next=pcur2;}return newhead;
}

优化：

我们每次都要对新创建的头结点判断是否为空。

有没有一种方法可以不用判断呢？：设置一个哨兵位就可以了

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {struct ListNode* pcur1=list1;struct ListNode* pcur2=list2;if(pcur1==NULL)return pcur2;if(pcur2==NULL)return pcur1;struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* tail = head;while(pcur1&&pcur2){if(pcur1->val<pcur2->val){tail->next=pcur1;tail=pcur1;pcur1=pcur1->next;}else{tail->next=pcur2;tail=pcur2;pcur2=pcur2->next;}}if(pcur1!=NULL){tail->next=pcur1;}else{tail->next=pcur2;}struct ListNode* newhead=head->next;free(head);return newhead;
}

六：链表分割

这题没给图，直接画图分析：

画图分析：

完整代码：

class Partition {
public:ListNode* partition(ListNode* pHead, int x) {ListNode* lesshead =(ListNode*)malloc(sizeof(ListNode));ListNode* lesstail=lesshead;ListNode* greaterhead=(ListNode*)malloc(sizeof(ListNode));ListNode* greatertail=greaterhead;ListNode* pcur=pHead;if(pcur==NULL)return NULL;while(pcur){if(pcur->val<x){lesstail->next=pcur;lesstail=pcur;}else {greatertail->next=pcur;greatertail=pcur;}pcur=pcur->next;}lesstail->next=greaterhead->next;greatertail->next=NULL;ListNode* newhead=lesshead->next;free(lesshead);free(greaterhead);return newhead;}
};

七：链表回文

首先这一题开一个900的数组也可以过，但是他并不符合空间复杂度O(1)。

然后我们说一下这一题的思路：先找中间结点，然后逆置，最后一一比较。

具体细节，请看下

画图分析：

完整代码：

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
struct ListNode* middleNode(ListNode* A)
{ListNode* slow = A;ListNode* fast = A;while(fast && fast->next){fast=fast->next->next;slow=slow->next;}return slow;
}
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* pprev = NULL;struct ListNode* pcur = head;struct ListNode* pnext;if(head){pnext = head->next;}while(pcur){pcur->next = pprev;pprev = pcur;pcur = pnext;if(pnext){pnext = pnext->next;}}return pprev;
}
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {ListNode* mid = middleNode(A);ListNode* rhead = reverseList(mid);ListNode* curA = A;ListNode* curR = rhead;while(curA && curR){if(curA->val != curR->val){return false;   }else{curA=curA->next;curR=curR->next;}}return true;}
};

八：链表相交

思路：遍历一遍求长度（同时判断是否会相交），长的走差值步，然后一起走直到两指针相同

这一题不可以用逆置做，想一想为什么？？

画图分析：

完整代码：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* curA = headA;struct ListNode* curB = headB;int lenA = 1; int lenB = 1;while(curA->next){lenA++;curA=curA->next;}while(curB->next){lenB++;curB=curB->next;}if(curA!=curB)return NULL;int gap = abs(lenA-lenB);struct ListNode* longlist = headA;struct ListNode* shortlist = headB;if(lenA < lenB){longlist = headB;shortlist = headA;}while(gap--){longlist=longlist->next;}while(longlist!=shortlist){longlist=longlist->next;shortlist=shortlist->next;}return longlist;
}

九：环形链表1

思路：快慢指针法，slow走1步fast走2步。如果相遇则带环，否则不带环

画图分析：

完整代码：

bool hasCycle(struct ListNode *head) {struct ListNode* slow = head;struct ListNode* fast = head;while(fast && fast->next){fast=fast->next->next;slow=slow->next;if(fast==slow)return true;}return false;
}

十：环形链表2

这一题有点数学题的意思。还是先说思路：还是先slow与fast走，等到两指针相遇，在再让一个指针从都走，另一个指针从相遇位置走，直到二者再次相遇即为如环点。

画图分析：

完整代码：

struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* slow = head;struct ListNode* fast = head;while(fast && fast->next){fast=fast->next->next;slow=slow->next;if(slow==fast){struct ListNode* cur = head;struct ListNode* curC = fast;while(cur!=curC){cur=cur->next;curC=curC->next;}return cur;}}return NULL;
}

十一：复杂随机链表的拷贝

这一次最难搞的是random指针。思路也不好想，大家还是借鉴一下大佬的思路吧。

思路：在每个节点后面插入一个一样的节点，定义cur 和 next指针 cur->next->radom=cur->radom->next，然后迭代往后。最后解开插入的结点。

画图分析：

完整代码：

struct Node* copyRandomList(struct Node* head) {struct Node* cur = head;//插入新节点while(cur){struct Node* newnode = (struct Node* )malloc(sizeof(struct Node));newnode->val = cur->val;newnode->next = cur->next;cur->next = newnode;cur = newnode->next;}//处理randomcur = head;while(cur){struct Node* newnode = cur -> next;if(cur->random==NULL){newnode->random = NULL;}else{newnode->random = cur->random->next;}cur = newnode->next;}//取新节点尾插，同时恢复原链表cur = head;struct Node* newhead = NULL;struct Node* newtail = NULL;while(cur){struct Node* newnode = cur->next;struct Node* next = newnode->next;if(newhead==NULL){newhead = newtail = cur->next;}else{newtail->next = newnode;newtail = newnode;}cur->next = newnode->next;cur = newnode->next;}return newhead;
}

完