目录

题目一、链表分割

1、解题思路

2、代码

题目二、相交链表

1、解题思路

2、代码

题目三、链表的回文结构

1、解题思路 

2、代码

题目一、链表分割

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

1、解题思路

首先，创建两个链表，分别放小于x的结点和大于x的结点（通过尾插的方式），再将两个链表链接起来。

注意：这里我们用两个带哨兵位的头结点的链表，可以很好地减少空指针的问题，减少需要考虑的特殊情况。

2、代码

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
#include 
#include 
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code herestruct ListNode*greaterGuard,*greaterTail,*lessGuard,*lessTail;greaterGuard=greaterTail=(struct ListNode*)malloc(sizeof(struct ListNode));lessGuard=lessTail=(struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode*cur=pHead;while (cur) {if(cur->valnext=cur;lessTail=lessTail->next;}else {greaterTail->next=cur;greaterTail=greaterTail->next;}cur=cur->next;}lessTail->next=greaterGuard->next;pHead=lessGuard->next;greaterTail->next=NULL;free(greaterGuard);free(lessGuard);return pHead;
}
};

题目二、相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

1、解题思路

第一步：分别计算两个链表的长度，求出两链表的长度差

第二步：让长链表的指针先走差距步

第三步：两个指针同时走，遇到相同的结点即为他们的公共结点。

2、代码

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode*tailA,*tailB;int lenA=1,lenB=1;tailA=headA;tailB=headB;while(tailA){tailA=tailA->next;lenA++;}while(tailB){tailB=tailB->next;lenB++;}if(tailB!=tailA){return NULL;}int gap=abs(lenA-lenB);struct ListNode*longList=headA,*shortList=headB;if(lenAnext;}while(longList!=shortList){longList=longList->next;shortList=shortList->next;}return longList;}

题目三、链表的回文结构

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

1、解题思路 

第一步：找到第二个中间结点，也就是后半链表的头。

第二步：把后半个链表逆置。

第三步：比较前后两链表是否相同。

2、代码

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:struct ListNode* middleNode(struct ListNode* head){struct ListNode*slow,*fast;slow=fast=head;while(fast!=NULL&&fast->next!=NULL){slow=slow->next;fast=fast->next->next;}return slow;
}
struct ListNode* reverseList(struct ListNode* head){struct ListNode*cur=head;struct ListNode*newhead=NULL;while(cur){struct ListNode*next=cur->next;cur->next=newhead;newhead=cur;cur=next;}return newhead;
}bool chkPalindrome(ListNode* head) {// write code herestruct ListNode*mid=middleNode(head);struct ListNode*rhead=reverseList(mid);while(head&&rhead){if(head->val!=rhead->val){return false;}head=head->next;rhead=rhead->next;}return true;}
};