目录
一、移除链表元素
1.常规情况：?
?用一指针记录cur指针的头一个节点，让prev->next指向cur->next，再free(cur)即可。
struct ListNode* cur = head;
struct ListNode* prev = head;
while(cur)
{
if(cur->val != val)
{
prev = cur;//这两句的顺序不能换
cur = cur->next;
}
else
{
prev->next = cur->next;
free(cur);
cur = prev->next;
}
}运行结果：?
?
?用VS验证测试用例:
int main()
{
struct ListNode* node1 = malloc(sizeof(struct ListNode));
struct ListNode* node2 = malloc(sizeof(struct ListNode));
struct ListNode* node3 = malloc(sizeof(struct ListNode));
struct ListNode* node4 = malloc(sizeof(struct ListNode));
node1->val = 7;
node2->val = 7;
node3->val = 7;
node4->val = 7;
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = NULL;
removeElements(node1, 7);
return 0;
}2. 考虑特殊情况
此处虽然改变了头结点，但是没有用双指针是因为返回了新的头。
struct ListNode* removeElements(struct ListNode* head, int val)
{
if(head == NULL)
{
return NULL;
}
struct ListNode* tmp = NULL;
while(head && head->val == val)
{
tmp = head;
head = head->next;
free(tmp);
tmp = NULL;
}
struct ListNode* cur = head;
struct ListNode* prev = head;
while(cur)
{
if(cur->val != val)
{
prev = cur;//这两句的顺序不能换
cur = cur->next;
}
else
{
prev->next = cur->next;
free(cur);
cur = prev->next;
}
}
return head;
}?这样写可能更好理解：
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* cur = head;
struct ListNode* prev = NULL;
while(cur)
{
if(cur->val != val)
{
prev = cur;
cur = cur->next;
}
else
{
struct ListNode* next = cur->next;
if(prev == NULL)//一开始就是cur->val==val
{
free(cur);//free掉头结点
head = next;//头指向下一个节点
cur = next;//cur也从下一个节点开始往后走
}
else
{
free(cur);
cur = next;
prev->next = next;
}
}
}
return head;
}?二、反转一个单链表
方法1：
当n2走到最后节点，n3是空了，那么在让n3= n3->next就是耍流氓了。
struct ListNode* reverseList(struct ListNode* head) {
if(head == NULL)
{
return NULL;
}
else if(head->next == NULL)
{
return head;
}
else
{
struct ListNode* n1 = NULL;
struct ListNode* n2 = head;
struct ListNode* n3 = head->next;
while(n2)
{
n2->next = n1;
n1 = n2;
n2 = n3;
if(n3)
{
n3 = n3->next;
}
}
return n1;
}
}
?方法2：
cur是空会直接返回newhead就是NULL
当时单节点的时候，返回头结点也符合，这样写不用单独去分类完成。
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* newhead = NULL;
struct ListNode* cur = head;
while(cur!=NULL)
{
struct ListNode* next = cur->next;
cur->next = newhead;
newhead = cur;
cur = next;
}
return newhead;
}三、链表的中间结点?
分链表节点是单数还是双数进行处理，但是单数的时候，fast->next == NULL也要停止往下走，返回slow即可。
struct ListNode* middleNode(struct ListNode* head){
if(head == NULL)
{
return NULL;
}
else if(head->next == NULL)
{
return head;
}
else
{
struct ListNode* slow = head;
struct ListNode* fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
}?四、链表中倒数第k个结点
链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)
快慢指针，让fast比slow先走k步，但是注意k的值，当k的值比链表长度还大，fast肯定会先走到NULL，那么返回NULL即可。
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
// write code here
if(pListHead==NULL){//如果链表为空，直接返回NULL
return NULL;
}
struct ListNode* fast = pListHead;
struct ListNode* slow = fast;
while(k--){
if(fast==NULL)
{//如果k的值大于链表长度直接返回NULL
return NULL;
}
fast=fast->next;//让fast比slow先走k步
}
while(fast!=NULL){
fast=fast->next;
slow=slow->next;
}
return slow;
}