# 题目

1 删除单链表给定值的所有节点 简单 LeetCode 双指针
2 反转单链表 简单 LeetCode 三指针或头插双指针
3 取单链表的中间结点 简单 LeetCode 快慢双指针
4 取单链表的倒数结点 简单 牛客网 双指针
5 合并单链表 简单 LeetCode 带哨兵位的尾插法
6 排序单链表 简单 牛客网 带哨兵位的尾插法
7 对称单链表 简单 牛客网 双指针+逆置
8 相交单链表 简单 LeetCode 普通的遍历求解
9 环形单链表 简单 LeetCode 快慢双指针

## 删除单链表给定值的所有节点

``````	if (head == NULL)
``````

``````typedef struct ListNode Node;
struct ListNode* removeElements(struct ListNode* head, int val)
{
//考虑头结点为空的情况
Node* prev = NULL;
while (cur)
{

if (cur->val == val)
{
{
//考虑头结点为删除点的情况
{
Node* delete = cur;
cur = cur->next;
free(delete);
}
else
{
Node* delete = cur;
cur = cur->next;
prev->next = cur;
free(delete);
}
}
}
else
{
prev = cur;
cur = cur->next;
}
}
}
``````

## 反转单链表

``````typedef struct ListNode Node;
{
//两个结点以下直接返回
{
}
Node* cur = NULL;
while (next)
{
Node* nextnext = next->next;
//反转
next->next = cur;
//遍历
cur = next;
next = nextnext;
}
return cur;
}
``````

``````typedef struct ListNode Node;
{
while (cur)
{
Node* next = cur->next;

//头插

cur = next;
}
}
``````

## 取单链表的中间结点

``````while(fast && fast->next)
{

}
``````

``````typedef struct ListNode Node;
{
{
}
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
``````

## 取单链表的倒数结点

``````typedef struct ListNode Node;
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k)
{
{
}
//next向前走k步,如果结点比k少，直接返回NULL
while (k-- && next)
{
next = next->next;
}
//为什么是k!=-1而不是k!=0,因为条件表达式k--执行了一次
if (k != -1 && next == NULL)
{
return NULL;
}
while (next)
{
cur = cur->next;
next = next->next;
}
return cur;
}
``````

## 合并单链表

``````typedef struct ListNode Node;
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
Node* newTail = NULL;
//依次排序
while (l1 && l2)
{
if (l1->val > l2->val)
{
newTail->next = l2;
newTail = l2;
l2 = l2->next;
}
else
{
newTail->next = l1;
newTail = l1;
l1 = l1->next;
}
}
//把剩下的全部链在新链表里
if (l1 == NULL)
{
newTail->next = l2;
}
else
{
newTail->next = l1;
}
}
``````

## 排序单链表

``````typedef struct ListNode Node, ListNode;
class Partition
{
public:
{
{
}
{
{
}
else
{
}
}
lessTail->next = NULL;
greatTail->next = NULL;
}
};
``````

## 对称单链表

``````typedef struct ListNode Node;
{
//两个结点以下直接返回
{
}
Node* cur = NULL;
while (next)
{
Node* nextnext = next->next;
//反转
next->next = cur;
//遍历
cur = next;
next = nextnext;
}
return cur;
}
class PalindromeList
{
public:
bool chkPalindrome(ListNode* A)
{
Node* prev = NULL;
Node* slow = A;
Node* fast = A;
while (fast && fast->next)
{
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
prev->next = NULL;
//千万注意将指针传入进去的是指针存放的地址，而不是指针的地址。
//是一份临时拷贝
//如果不是二级指针接受，返回的时候需要slow来接受返回地址。
//好好想想，千万注意。
slow = reverseList(slow);
{
return false;
slow = slow->next;
}
return true;
}
};
``````

## 相交单链表

``````typedef struct ListNode Node;
{
return NULL;
int lA = 0;
int lB = 0;
while (curA)
{
lA++;
curA = curA->next;
}
while (curB)
{
lB++;
curB = curB->next;
}
//只要判断是否lA大于lB即可
//因为最前面的赋值的默认情况是lB大于lA
if (lA > lB)
{
}
int gap = abs(lA-lB);
while(gap--)
{
longList = longList->next;
}

while (shortLlist && longList)
{
if (shortLlist == longList)
return longList;
shortLlist = shortLlist->next;
longList = longList->next;

}
return NULL;

}
``````

## 环形单链表

``````typedef struct ListNode Node;
{
return false;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
return true;
}
return false;
}
``````