目录

206.反转链表

876.链表的中间节点

链表中倒数第k个节点

CM11链表分割

OR36 链表的回文

206.反转链表

给你单链表的头节点head,请你反转链表，并返回反转后的链表。

 实现如下结果：

 思路：

取链表中的节点头插：

代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* reverseList(struct ListNode* head){
struct ListNode *cur=head;
struct ListNode *plist=NULL;
while(cur)
{struct ListNode *next=cur->next;cur->next=plist;//cur->next指向plist的地址plist=cur;          //plist 指向cur的地址，刚上面的一行代码和这一行代码使得链表的空间相连cur =next; 
}
return plist;
}/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* reverseList(struct ListNode* head){
struct ListNode *cur=head;
struct ListNode *plist=NULL;     //作为新的头节点
while(cur)
{struct ListNode *next=cur->next;     //记住cur的下一个节点cur->next=plist;//      头插plist=cur;          //换头cur =next;          //将原来cur->next节点的地址赋给cur
}
return plist;
}

876.链表的中间节点

给定一个头节点为head的非空单链表，返回链表的中间节点。如果有两个中间节点，则返回第二个中间节点。要求只能遍历一遍

思路：用快慢指针找到中间节点，定义两个结构体变量指针slow,fast。

slow每次走一步，fast每次走两步。当fast->next为空的时候,则链表长度为奇数,那么slow就是中间节点；当fast为空时，链表的长度为偶数，那么中间节点有两个，则返回第二个中间节点。

代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* middleNode(struct ListNode* head){
struct ListNode *fast,*slow;
slow=fast=head;
while(fast&&fast->next)
{slow=slow->next;fast=fast->next->next;
}
return slow;
}

链表中倒数第k个节点

输入一个链表，输出该链表中第k个节点

思路：定义结构体指针变量slow,fast,让fast先走k部,然后它们都各自每次向后走一步，当fast为空的时候，返回slow,此时slow就为链表中第k个节点。也可以让fast先走k-1步，当fast->next为空的时候，slow就是链表中第k个节点。

在这里需要注意的就是要注意k的值是否大于链表的长度，如果大于则返回NULL.

 代码：

struct ListNode*FindKthToTail(struct ListNode*pListHead,int k)
{struct ListNode*fast,slow;fast=slow=pListHead;while(k--)//让fast先走k步{//链表可能没有k步长if(fast==NULL){return NULL;}fast=fast->next;}while(fast)//当fast为空{fast=fast->next;slow=slow->next;}
return slow;
}

CM11链表分割

描述：

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

思路：

这道题用带哨兵位的链表求解，将所有小于x的节点尾插到第一个哨兵位节点后面；其余的尾插到第二个带哨兵位节点后面；最后将两个链表链接，返回第一个哨兵位节点后一个节点。

这里需要注意的是，在最后尾插结束时记得将第二个链表的尾节点的下一个节点置空（即上图的greaterTail的下一个节点置空），因为尾插结束，greaterTail->next还指向链表中的其他节点，如果不置空，会形成环。

代码： 

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

OR36 链表的回文

描述：

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

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

 思路：将链表的后半部分的节点逆置，再将前半部分的值和后半部分的值相比。因为额外的空间复杂度为O(1)，所以不能整体逆置，整体逆置要重新开辟一个和原来一样长的链表空间。所以这里将后半部分的节点逆置之后就可以比较了。

代码：

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:struct ListNode* middle(struct ListNode* phead)  //返回中间值{struct ListNode*fast,*slow;fast=slow=phead;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}return slow;}struct ListNode*reverse(struct ListNode*phead)
{struct ListNode*cur=phead;struct ListNode*rehead=NULL;while(cur){struct ListNode*next=cur->next;//头插cur->next=rehead;rehead=cur;cur=next;}return rehead;
}bool chkPalindrome(ListNode* A){struct ListNode*mid=middle(A);struct ListNode*rehead=reverse(mid);while(A && rehead){if(A->val!=rehead->val)return false;A=A->next;rehead=rehead->next;}return true;// write code here}
};