一、160. 相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。 图示两个链表在节点 c1 开始相交 题目数据 保证 整个链式结构中不存在环。 注意，函数返回结果后，链表必须 保持其原始结构 。 自定义评测： 评测系统 的输入如下（你设计的程序 不适用 此输入）： intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0 listA - 第一个链表 listB - 第二个链表 skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数 skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数 评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
int sumA=0;
int sumB=0;
struct ListNode*curA=headA;
struct ListNode*curB=headB;
while(curA!=NULL)//求headA的长度
{
sumA ;
curA=curA->next;
}
while(curB!=NULL)//求headB的长度
{
sumB ;
curB=curB->next;
}
int k=sumA>sumB?sumA-sumB:sumB-sumA;//长度差
struct ListNode* longlist=headA;
struct ListNode* shortlist=headB;
if(sumB>sumA)//无论怎么变，longlist都是最长的那个
{
longlist=headB;
shortlist=headA;
}
while(k--)//将longlist向后移长度次
{
longlist=longlist->next;
}
while(longlist!=NULL&&shortlist!=NULL)
{
if(longlist==shortlist)
{
return longlist;
}
longlist=longlist->next;
shortlist=shortlist->next;
}
return NULL;
}
二、面试题 02.04. 分割链表
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。 你不需要 保留 每个分区中各节点的初始相对位置。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* partition(struct ListNode* head, int x){
struct ListNode* lesshead,*lesstail;
struct ListNode*morehead,*moretail;//都是带哨兵位的头节点
lesshead=lesstail=(struct ListNode*)malloc(sizeof(struct ListNode));//设立四个头节点
morehead=moretail=(struct ListNode*)malloc(sizeof(struct ListNode));//分别代表比x小的和比x大的
morehead->next=NULL;
lesshead->next=NULL;
struct ListNode*cur=head;
while(cur!=NULL)
{
if(cur->val<x)//如果比x小就传入lesstail中
{
lesstail->next=cur;
lesstail=lesstail->next;
}
else
{
moretail->next=cur;//如果比x大就传入moretail中
moretail=moretail->next;
}
cur=cur->next;
}
lesstail->next=morehead->next;//lesstail的尾来连接morehead的下一个
moretail->next=NULL;//因为我们不知道此时的最后一个节点是否为原节点的最后一个 所以需要置空
struct ListNode*prev=lesshead->next;//接收lesshead的后一个节点
free(lesshead);
free(morehead);
return prev;
}
三、876. 链表的中间结点
代码语言：javascript复制给定一个头结点为 head 的非空单链表，返回链表的中间结点。 如果有两个中间结点，则返回第二个中间结点。
示例 1： 输入：[1,2,3,4,5] 输出：此列表中的结点 3 (序列化形式：[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。 注意，我们返回了一个 ListNode 类型的对象 ans，这样： ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL. 示例 2： 输入：[1,2,3,4,5,6] 输出：此列表中的结点 4 (序列化形式：[4,5,6]) 由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* middleNode(struct ListNode* head){
struct ListNode*fast=head;//快慢指针 快指针一次走两步 慢指针一次走一步
struct ListNode*slow=head;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
}
return slow;
}
四、234. 回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool isPalindrome(struct ListNode* head){
struct ListNode*fast=head;
struct ListNode*slow=head;
while(fast&&fast->next)//寻找中间节点
{
fast=fast->next->next;
slow=slow->next;
}
struct ListNode*n1=NULL;
struct ListNode*n2=slow;
struct ListNode*n3=slow->next;
while(n2!=NULL)//逆置中间节点后的节点
{
n2->next=n1;
n1=n2;
n2=n3;
if(n3!=NULL)
{
n3=n3->next;
}
}
while(head&&n1)//如果从头开始的与从尾开始的都相等就是 反之就不是
{
if(head->val==n1->val)
{
head=head->next;
n1=n1->next;
}
else
{
return false;
}
}
return true;
}
