typedef struct ListNode
{
int val;
struct ListNode* next;
}ListNode; //节点
void PrintList(ListNode* head)
{
while (head!=NULL) {
printf("%d->",head->val);
head = head->next;
}
printf("NULLn");
} //打印每个节点数据
一、删除节点
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
思路1：直接遇到节点后，把节点前后相连接，把节点让出来释放掉。
struct ListNode* removeElements(struct ListNode* head, int val) {
struct ListNode* p = head;
struct ListNode* pre = NULL;
while (p) {
if (val == p->val) {
if (p == head) {
head = head->next;
free(p);
p = head;
}
else {
pre->next = p->next;
free(p);
p = pre->next;
}
}
else {
pre = p;
p = p->next;
}
}
return head;
}
PS：因为要让节点前后连接，所以注意要保留前一个节点的指针。
如果是头节点删除，那么不用连接前后节点，直接把链表头节点的下一个节点当成新的头节点，然后删除原来的节点。
如果节点不是要删除的节点，让指针往下走继续找。
测试：
void test1()
{
ListNode* p1 = (ListNode*)malloc(sizeof(ListNode));
p1->val = 1;
ListNode* p2 = (ListNode*)malloc(sizeof(ListNode));
p2->val = 2;
ListNode* p3 = (ListNode*)malloc(sizeof(ListNode));
p3->val = 3;
ListNode* p4 = (ListNode*)malloc(sizeof(ListNode));
p4->val = 4;
ListNode* p5 = (ListNode*)malloc(sizeof(ListNode));
p5->val = 5;
p1->next = p2;
p2->next = p3;
p3->next = p4;
p4->next = p5;
p5->next = NULL;
PrintList(p1);
p1 = removeElements(p1,4);
PrintList(p1);
}
int main()
{
test1();
return 0;
}
思路2：如果不是要查找的节点把节点拿下来，头插入另一个链表。
struct ListNode* removeElements(struct ListNode* head, int val){
struct ListNode* tail=NULL;
struct ListNode* p=head;
head=NULL;
while(p){
if(p->val==val){
struct ListNode* del=p;
p=p->next;
free(del);
}
else{
if(tail==NULL){
tail=p;
p=p->next;
head=tail;
}
else{
tail->next=p;
tail=tail->next;
p=p->next;
}
}
}
if(tail!=NULL)
tail->next=NULL;
return head;
}
PS：刚开始另一个链表为NULL，第一个拿下来的节点就为头节点。全部插入完成后要让尾节点指向NULL。
这还要定义一个指针用来保存另一个链表的尾结点，这样每次插入节点就不用遍历尾节点了。
如果给到是空链表，那么tail指针这里是不能让其Next指针为NULL的，所以这里要判断一下。
二、反转一个单链表给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
思路1：直接把遇到的节点拿下来头插进另一个链表。
插入完就会发现链表已经被翻转过来了
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* p = head;
struct ListNode* h = NULL;
struct ListNode* pre = NULL;
while (p) {
pre = p;
p = p->next;
pre->next = h;
h = pre;
}
return h;
}
测试：
思路2：设三个指针，一个指向要逆转指针节点的下一个，一个指向另一个链表的尾结点，一个指向当前链表的节点。当现在链表的节点插入到另一个链表后，把下一个节点指针赋值给它继续插入。
ListNode* rL_2(ListNode* head)
{
if (!head)
return head;
struct ListNode* p = head;
struct ListNode* pre = NULL;
struct ListNode* next = p->next;
while (p) {
p->next = pre;
pre = p;
p = next;
if (next != NULL)
next = next->next; //防止越界
}
return pre;
}
刚开始pre指向NULL，第一个插入的节点相当于链表最后的尾节点。
PS：其实会发现这个方法也相当于头插法，只不过把指针指向的下一个节点提前保存了，赋值的顺序也放后面了。
赋值到最后的时候next此时为NULL，再赋值给p指针，再往后走一次，next会越界。所以这里只能用p是否为空来判断循环结束并且要判断next是否已为NULL，如果为NULL就不让next往下走了。
三、返回链表的中间结点给定一个头结点为 head 的非空单链表，返回链表的中间结点。
思路：快慢指针，一个指针走一个节点，一个指针走两个节点，那么第二个指针走到尾结点，那么前一个指针就刚好在链表中间的节点。
struct ListNode* middleNode(struct ListNode* head){
struct ListNode* p1=head;
struct ListNode* p2=head;
while( p2 && p2->next){
p1=p1->next;
p2=p2->next->next;
}
return p1;
}
因为要存在链表长度是奇数偶数的情况，也就是说p2指针有可能走到尾结点，或者走到尾结点的下一个NULL节点。所以判断时都要判断一个，当p2为空或者p2下一个节点为空，说明循环结束。
测试：
四、链表中倒数第k个结点输入一个链表，输出该链表中倒数第k个结点。
思路：快慢指针，第二个指针比第一个指针长k，那么第二个指针到链表结束，第一个指针就是倒数第k个节点。
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
if(!pListHead || k<=0)
return NULL;
struct ListNode* p1=pListHead;
struct ListNode* p2=pListHead;
while(k--){
if(p2)
p2 = p2->next;
else
return NULL;
}
while(p2){
p1=p1->next;
p2=p2->next;
}
return p1;
}
如果给到链表为空或者k为负数，返回NULL指针。
当k刚好等于链表长度时p2指向NULL，但是先判断的k==0，所有不会返回NULL，这时候，p1刚好就是链表头节点。
如果k大于链表长度，那么p2越界继续往后走会越界，所以判断p2为空时，返回NULL
测试：
拓展：哨兵位（虚设节点）
这里以第一题，删除节点来说，会发现如果删除头节点的时候会多判断一次。在链表前面设置一个哨兵位，可以减少判断和操作。
哨兵位不存储数据，链表操作从哨兵节点下一个节点开始，那么就会简化所以要判断头节点的情况。
返回的时候返回哨兵节点的下一个即可，当然要记得释放掉哨兵节点
struct ListNode* removeElements(struct ListNode* head, int val){
struct ListNode* p=head;
struct ListNode* tail=(struct ListNode*)malloc(sizeof(struct ListNode));
head=tail;
tail->next=NULL;
while(p){
if(p->val==val){
struct ListNode*del=p;
p=p->next;
free(del);
}
else{
tail->next=p;
tail=p;
p=p->next;
}
}
tail->next = NULL;//尾节点记得置空
struct ListNode* re=head;
head=head->next;
free(re);
return head;
}
