@TOC

一、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. 链表的中间结点

给定一个头结点为 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;
}