@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; }
在这里插入图片描述
