【Leedcode】数据结构中链表必备的面试题（第三期）

【Leedcode】数据结构中链表必备的面试题（第三期）

---

---

一、第一题

1.题目

CM11 链表分割 如下（示例）：

现有一链表的头指针ListNode*pHead，给一定值x，
编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。 

---

2.思路

1.使用两个哨兵位的头结点lesshead和greathead，把小于4的连接到lesshead后面，大于4的链接到greathead后面；
2.再把小于4的最后一个连接到大于4的第一个：具体如下图

---

---

注意：如下图！

---

3.源代码

代码如下（示例）：

struct ListNode {int val;struct ListNode *next;
};
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {struct ListNode* lessHead, *lessTail, *greaterHead, *greaterTail;lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));lessTail->next = greaterTail->next = NULL;struct ListNode* cur = pHead;while (cur) {if (cur->val < x) {lessTail->next = cur;lessTail = lessTail->next;}else {greaterTail->next = cur;greaterTail = greaterTail->next;}cur = cur->next;}lessTail->next = greaterHead->next;greaterTail->next = NULL;struct ListNode* list = lessHead->next;free(lessHead);free(greaterHead);return list;}
};

---

二、第二题

1.题目

OR36 链表的回文结构 如下（示例）：

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。 

---

2.思路

(1)第一种情况：偶数个链表

---

---

(2)第二种情况：奇数个链表

---

3.源代码

(1)链表的中间结点的实现

876. 链表的中间结点的实现 如下（示例）：

struct ListNode
{int val;struct ListNode *next;
}
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slow,*quick;slow=quick=head;while(quick && quick->next){slow= slow->next;quick= quick->next->next;}return slow;
}

---

(2)反转链表的实现

206. 反转链表的实现 如下（示例）：

struct ListNode 
{int val;struct ListNode *next;
};
struct ListNode* reverseList(struct ListNode* head)
{//第二种方法struct ListNode* newhead=NULL;struct ListNode* cur=head;while(cur){struct ListNode* next=cur->next;cur->next=newhead;newhead=cur;cur=next;}return newhead;
}

---

(3)链表比较函数的实现

代码如下（示例）：

class PalindromeList {
public:bool chkPalindrome(ListNode* A) {struct ListNode* mid =middleNode(A);struct ListNode* rHead =reverseList(mid);struct ListNode* curA=A;struct ListNode* curR = rHead;while( curA && curR){if(curA -> val != curR ->val){return false;}else {curA=curA->next;curR =curR-> next;}}return true;}
};

---

(4)整体源代码

代码如下（示例）：

struct ListNode 
{int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slow,*quick;slow=quick=head;while(quick && quick->next){slow= slow->next;quick= quick->next->next;}return slow;
}
struct ListNode* reverseList(struct ListNode* head)
{//第二种方法struct ListNode* newhead=NULL;struct ListNode* cur=head;while(cur){struct ListNode* next=cur->next;cur->next=newhead;newhead=cur;cur=next;}return newhead;}
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {struct ListNode* mid =middleNode(A);struct ListNode* rHead =reverseList(mid);struct ListNode* curA=A;struct ListNode* curR = rHead;while( curA && curR){if(curA -> val != curR ->val){return false;}else {curA=curA->next;curR =curR-> next;}}return true;}
};

---

总结

以上就是今天要讲的内容，本文介绍数据结构中链表必备的面试题（第三期）
如果我的博客对你有所帮助记得三连支持一下，感谢大家的支持！