目录
3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。
10. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL
1. 删除链表中等于给定值 val 的所有节点。
leetcode 203 移除链表元素
typedef struct ListNode Node;
struct ListNode* removeElements(struct ListNode* head, int val){
Node* cur = head;
Node *prev = NULL;//保存cur的前一个结点
while(cur)
{
if(cur->val == val)
{
if(NULL == prev)
{
//需要删除的cur刚好是链表第一个结点，此时prev是空
//需要修改head的指向
head = cur->next;
free(cur);
cur = head;
}
else
{
//删除cur
//让prev的next指向此时cur的next
prev->next = cur->next;
free(cur);
//将prev赋值给cur
cur = prev->next;
}
}
else
{
prev = cur;
cur = cur->next;
}
}
return head;
}2. 反转一个单链表。
leetcode 206 反转链表
typedef struct ListNode Node;
struct ListNode* reverseList(struct ListNode* head){
Node* prev = NULL;
Node* cur = head;
Node* next = NULL;
//以左图为例子，此时，cur在1，其他在null
while(cur)
{
next = cur->next; //next在2，cur在1，prev在空
cur->next = prev;//改变链表指向，让cur指向空
prev = cur; //prev在1
cur = next;//cur在2，依次改变链表每个结点指向
}
return prev;
}
3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
leetcode 876
给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
思路:
给两个指针fast slow，fast每次走2步，slow走一步,fast到末尾，slow在中间
typedef struct ListNode Node;
struct ListNode* middleNode(struct ListNode* head){
Node* fast = head;
Node* slow = head;
//fast和接下来2步都不为空
//fast不为null，可以保证fast第一步成功
//fast->next 不为空，保证第二部走成功
while(fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
}
return slow;
}拓展：要求假设返回中间的第一个结点
Node* fast = head;
Node* slow = head;
Node* prev =NULL;
while(fast && fast->next)
{
fast = fast->next->next;
prev = slow;
slow = slow->next;
}
if(fast) //总数是奇数
{
return slow;
}
else //总数是偶数
{
return prev;
}4. 输入一个链表，输出该链表中倒数第k个结点。
最优思路：先让front走k步，再让back和front同时走，当front到末尾,back就是倒数第k结点
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
// write code here
//先让front走k步，再让back和front同时走，当front到末尾,back就是倒数第k结点
//1.对参数进行检测
if(NULL ==pListHead || k <= 0)
return NULL;
//2.定义两个指针
struct ListNode* front = pListHead;
struct ListNode* back = pListHead;
//注意K可能会大于链表长度
while(k)
{
if(NULL == front)
return NULL;
front = front->next;
k--;
}
while(front != NULL)
{
front = front->next;
back = back->next;
}
return back;
}5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
（Leetcode 21.合并两个有序链表）
思路：
1.先创建一个新的链表
2.让cur1 和 cur2遍历两个链表，遇到的节点逐个比较，将值小的节点往新链表的末尾tail进行尾插
3.上述循环结束后，要判断有无链表还有剩余元素，把剩余的元素尾插到新链表的末尾。
typedef struct ListNode Node;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
if(NULL == list1)
return list2;
if(NULL == list2)
return list1;
//走到这里，说明两个链表均不为空,需要合并
Node* pNewList =NULL;
Node* cur1 = list1;
Node* cur2 = list2;
//在pnewlist中插入第一个节点，第一个节点要修改pnewlist的指向
if(cur1 -> val <= cur2->val)
{
pNewList = cur1;
cur1 = cur1->next;
}
else
{
pNewList = cur2;
cur2 = cur2->next;
}
Node* tail = pNewList;//新链表的尾部
//让cur1 和 cur2遍历两个链表，遇到的节点逐个比较
//将值小的节点往新链表的末尾tail进行尾插
while(cur1 && cur2)
{
if(cur1->val <= cur2->val)
{
tail->next = cur1;
cur1 = cur1->next;
}
else
{
tail->next = cur2;
cur2 = cur2->next;
}
tail = tail->next;
}
if(cur1)
{
tail->next =cur1;
}
else if(cur2)
{
tail->next = cur2;
}
else{
return pNewList;
}
return pNewList;
}6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。
OJ链接
思路：
1.创建两个链表，一个链表尾插值小于x的节点，另一个链表中插值大于等于x的节点
2.遍历原链表，将链表中的节点往两个新链表中尾插--新链表最好将其给成带头节点的单链表
3.将两个链表拼接
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
if(NULL == pHead)
return pHead;
//less链表中尾插小于x的节点
ListNode less(0);
ListNode* lessTail = &less;
//尾插大于等于x的节点
ListNode greater(0);
ListNode* greaterTail = &greater;
ListNode* cur = pHead;
//利用cur去遍历phead
while(cur)
{
if(cur->val < x)
{
lessTail->next = cur;
lessTail = lessTail->next;
}
else
{
greaterTail->next = cur;
greaterTail = greaterTail->next;
}
cur = cur->next;
}
//拼接两个链表
lessTail ->next = greater.next;
greaterTail->next = NULL;
return less.next;
}
};7. 链表的回文结构。
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。OJ链接
思路1：
题目中条件：保证链表长度小于等于900，所以额外空间创建如下 为o(1)
1.给一个900的Int类型的数组
2.遍历链表，让每个节点的值放入数组
3.检测数组中保存的元素是否为回文结构
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
int array[900];
ListNode* cur = A;
int size = 0;
//遍历链表
while(cur)
{
array[size] = cur-> val;
cur = cur->next;
size++;
}
int left = 0;
int right = size-1;
while(left < right)
{
if(array[left] != array[right])
{
return false;
}
else
{
left++;
right--;
}
}
return true ;
}
};对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。（去掉一个条件）
思路2：
1.找到链表的中间节点，从中间节点的位置将链表分开，形成2个链表---->找中间节点:采用快慢指针ok
2.对后半部分进行逆置---链表的逆置ok
3.将两个链表从前往后逐个节点进行比对，如果比对之后发现所有节点的值域都相同，则是回文链表，否则不是
4.将链表还原成原链表
注意:一般情况下不要破坏链表的结构，如果破坏了最后最好将其恢复
class PalindromeList {
public:
ListNode* getMiddleNode(ListNode* plist)
{
ListNode* fast = plist;
ListNode* slow = plist;
while(fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
ListNode* reverseList(ListNode* plist)
{
ListNode* cur = plist;
ListNode* prev = NULL;
ListNode* next = NULL;
while(cur)
{
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
bool chkPalindrome(ListNode* A)
{
if(NULL == A || NULL == A->next)
return true;
//找到A链表中间节点，然后从中间节点的位置将其断开
ListNode* list1 = A;
ListNode* midNode = getMiddleNode(A);
ListNode* list2 = midNode->next;
midNode->next = NULL;
//将后半部分进行逆置
list2 = reverseList(list2);
//将list1和list2中的节点逐个比较
bool ret = true;
ListNode* cur1 = list1;
ListNode* cur2 = list2;
while(cur1 && cur2)
{
if(cur1->val != cur2->val)
{
ret = false;
break;
}
cur1 = cur1->next;
cur2 = cur2->next;
}
//还原链表
list2 = reverseList(list2);
midNode->next = list2;
return ret;
}
};8. 输入两个链表，找出它们的第一个公共结点。
leetcode 160.相交链表
下面是两个节点相交的各类情况：
在相交的情况下，求交点的方式：
1.让较长的链表先走两个链表的差值步数
2.在让两个链表同时往后走，直到遇到地址相同的交点
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
//参数检测，如果有一个链表为空，不可能相交
if(NULL == headA || NULL == headB)
{
return NULL;
}
//1.检测headA和headB是否相交
//分别找到两个链表最后一个节点，相同就相交，不同则不交
struct ListNode* curA = headA;
int sizeA = 1;
int sizeB = 1;
while(curA ->next)
{
curA = curA->next;
sizeA++;
}
struct ListNode* curB = headB;
while(curB->next)
{
curB = curB->next;
sizeB++;
}
if(curB != curA)
return NULL;
//2.执行到此处说明相交
int gap = sizeA - sizeB;
curA = headA;
curB = headB;
if(gap > 0)
{
//headA长
while (gap--)
{
curA = curA->next;
}
}
else
{
while(gap++)
{
curB = curB->next;
}
}
while(curA != curB)
{
curA = curA->next;
curB = curB->next;
}
return curA;
}9. 给定一个链表，判断链表中是否有环。
leetcode 141，环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
思路：
快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表其实位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾
为什么快指针每次走两步，慢指针走一步可以？
假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可
能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动
一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在满指针走到一圈之前，
快指针肯定是可以追上慢指针的，即相遇
快指针如果走3、4步，可能存在永远不能遇到的可能
bool hasCycle(struct ListNode *head) {
struct ListNode* fast = head;
struct ListNode* slow = head;
while(fast && fast->next)
{
fast= fast->next->next;
slow = slow->next;
if(fast == slow)
return true;
}
return false;
}10. 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL
leetcode 142环形链表2
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode* fast = head;
struct ListNode* slow = head;
int hasCycle = 0; //标记链表是否带环
while(fast && fast->next)
{
fast= fast->next->next;
slow = slow->next;
if(fast == slow)
{
hasCycle = 1;
break;
}
}
if(!hasCycle)//链表不带环
return NULL;
struct ListNode* pH = head;
struct ListNode* pM = fast; //相遇点
while(pH != pM)
{
pH = pH->next;
pM = pM->next;
}
return pM;
}