LeetCode(2)-反转链表、删除链表中等于val的节点、返回链表中的中间节点

一、反转链表

. - 力扣（LeetCode）

解法1：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {if(head==NULL)return NULL;ListNode* n1;ListNode* n2;ListNode* n3;n1=NULL;n2=head;n3=n2->next;while(n2){n2->next=n1;n1=n2;n2=n3;if(n3)n3=n3->next;//防止对空指针解引用}return n1;
}

定义三个节点指针，n1,n2,n3 ；目的是让n1成为新的头节点，让n2的next指向n1，让n1=n2，n3=n3->next，那么循环一次之后的链表是NULL<-1 2->3->NULL(此处->表示箭头),第一次循环之后n1数据域是1，n2数据域是2，n3的数据域是3;

在第二次循环结束后，链表变成NULL<-1<-2 3->NULL ,n1数据域是2，n2数据域是3，n3是NULL；

第三次循环时，链表变成 NULL<-1<-2<-3 NULL ；n1数据域是3，n2是NULL，n3是NULL，循环结束

最终实现了链表的翻转。

解法2：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {if(head==NULL) return NULL;ListNode* pcur=head;ListNode* newhead=NULL;while(pcur){ListNode* next=pcur->next;pcur->next=newhead;newhead=pcur;pcur=next;}return newhead;
}

遍历原链表，创建一个新的头节点，利用头插的方法实现翻转。

二、删除链表中等于val的节点

. - 力扣（LeetCode）

解法：

创建一个新链表，遍历原链表，把节点的val值不为val的尾插进入新的链表；

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {if(head==NULL) return head;ListNode* pcur=head;ListNode* newhead=NULL;ListNode* newtail=NULL;while(pcur){if(pcur->val!=val){if(newhead==NULL){newhead=newtail=pcur;}else{newtail->next=pcur;newtail=pcur;}}pcur=pcur->next;}if(newtail!=NULL)newtail->next=NULL;return newhead;
}

三、返回链表中的中间节点

https://leetcode.cn/problems/middle-of-the-linked-list/description/

解法：

快慢指针，定义两个指针，利用循环，慢指针每次走一步，快指针每次走两步，最后快指针的next指针为NULL或者是快指针本身为NULL时，结束循环，返回慢指针；

原理：快指针走完链表之后，慢指针刚好走一半

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {if(head==NULL) return head;else{ListNode* fast=head;ListNode* slow=head;while(fast && fast->next){slow=slow->next;fast=fast->next->next;}return slow;}
}

要注意：当链表为奇数个时，只需要当快指针的next为NULL时返回慢指针；当链表为偶数个时当快指针为NULL时返回慢指针；循环条件要把fast写在fast->next前面，因为fast为NULL时不能解引用，此时先写fast->next错误。