目录

一、移除链表元素

1.常规情况： 

2. 考虑特殊情况

 二、反转一个单链表

方法1：

 方法2：

三、链表的中间结点 

一、移除链表元素

203. 移除链表元素 - 力扣（LeetCode）

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;
}

 二、反转一个单链表

206. 反转链表 - 力扣（LeetCode）

方法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;
}

三、链表的中间结点 

876. 链表的中间结点 - 力扣（LeetCode）

分链表节点是单数还是双数进行处理，但是单数的时候，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;
    }
}