单链表OJ题

单链表OJ题（文字解读 + 图解）

1. 移除链表元素
2. 反转链表
3. 链表的中间结点
4. 返回倒数第 k 个节点
5. 合并两个有序链表

1. 移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点。
OJ链接=>

struct ListNode* removeElements(struct ListNode* head, int val)；

这题当然可以暴力遍历，将值一一对比，相等的删除，并重新链接。但还有更优的思路：

定义两个指针(slow,fast);
fast先走，如果fast指向的val和其相等，则让slow指向fast的下一个后fast再走；如果不相等，则让slow指向fast指向的位置后发射台再走；
最后再分一些特殊情况。

struct ListNode* removeElements(struct ListNode* head, int val) {
    
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    //头为空，直接返回空
    if(head == NULL)
        return  NULL;
    while(fast)
    {
        if(fast->val == val)
        {
            slow->next = fast->next;
            fast = fast->next;
        }
        else
        {
            slow=fast;
            fast=fast->next;
        }
    } 
    //当头结点就是val时并且头结点下一个结点为空，直接返回空
    if(head->val == val&&head->next==NULL)
        return NULL;
    //当头结点就是val时并且头结点下一个结点不去为空，直接返回头节点的下一个节点
    else if(head->val == val&&head->next!=NULL)
        return head->next;
    else 
        return head;
}

最后一定要分情况，不然OJ有些测试用例通过不了。

2. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
OJ链接=>

struct ListNode* reverseList(struct ListNode* head)；

这题的最优解:

创建3个指针，第一个指针n1指向空，第二个指针n2指向头节点，第三个指针n3指向头节点的下一个节点；
先将n2指向n1，再让n1指向n2，n2指向n3，再循环往后走；

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* n1 = NULL;
    struct ListNode* n2 = head;
    
    while(n2)
    {
        struct ListNode* n3 = n2->next;
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        
    }
    return n1;
}

最后一次，当n3赋值给n2时，n2指向空，所以循环结束条件n2!=NULL。如果将n3放在循环外创建可能会造成空指针，因为数组可能只有一个元素或者就没有元素，这样n3就没有用了。

3. 链表的中间结点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。
OJ链接=>

struct ListNode* middleNode(struct ListNode* head) ；

这题还是快慢指针问题:
让一个指针从头节点开始一次走一步，让第二个指针从头节点开始一次走两步，走到尾时，慢指针刚好走到中间节点。

struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        
    }
    return slow;
}

当节点个数为奇数个时，循环终止条件为fast->next != NULL；当节点个数为偶时，循环终止条件为fast != NULL，将两种情况合并。

4. 返回倒数第 k 个节点

实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
OJ链接=>

int kthToLast(struct ListNode* head, int k)；

这是一道经典的面试题，最优思路为:先让一个指针从头节点走k步，再让一个指针从头节点开始和前一个指针同时走，当走到尾，慢指针指向的就是我们要的。
在这里插入图片描述

int kthToLast(struct ListNode* head, int k){
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while(k--)
    {
        fast = fast->next;
    }
    while(fast)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow->val;
}

循环结束条件为当fast == NULL.

5. 合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
OJ链接=>

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2);

解题思路：
此题可以先创建一个空链表，然后依次从两个有序链表中选取最小的进行尾插操作进行合并。
在这里插入图片描述

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode* head = NULL,*tail = NULL;
    //特殊情况先出
    if(list1 == NULL)
    {
        return list2;
    }
    if(list2 == NULL)
    {
        return list1;
    }
    
    while(list1 && list2)
    {
        if(list1->val < list2->val)
        {
        	//第一次插入
            if(tail == NULL)
            {
                head = tail = list1;
            }
            else
            {
            	//后续取较小的尾插
                tail->next = list1;
                tail = tail->next; 
            }
            list1 = list1->next;
        }
        else
        {
            if(tail == NULL)
            {
                head = tail = list2;
            }
            else
            {
                tail->next = list2;
                tail = tail->next; 
            }
            list2 = list2->next;
        }
    }
    //当list2走完，list1还有节点时直接尾插
    if(list1)
    {
        tail->next = list1;
    }
    //当list1走完，list2还有节点时直接尾插
    if(list2)
    {
        tail->next = list2;
    }
    return head;
}