【数据结构】链表OJ

Yan-英杰的主页

悟已往之不谏知来者之可追

编辑

编辑二、分享：OJ调试技巧

编辑三、链表的中间结点

编辑四、链表中倒数第k个结点

一、移除链表元素

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：

输入：head = [], val = 1
输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

提示：

列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50

方法一：

代码解析:

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;
   while(cur)
   {
        if(cur->val != val)
        {
            prev = cur;
            cur = cur->next;
        }
        else
        {
            if(prev == NULL)
            {
                head = cur->next;
                free(cur);
                cur = head;
            }
            else
            {
               prev->next = cur->next;
               free(cur);
               cur = prev->next;
            }
        }
   }
   return head;
}

画图解析:

方法二：

代码解析：

struct ListNode* removeElements(struct ListNode* head, int val){
    if(head == NULL)
    {
        return NULL;
    }
  struct ListNode* newHead = NULL,*tail = NULL;
  struct ListNode* cur = head;
        while(cur)
        {
           if(cur->val != val)
            {   //尾插
              if(tail == NULL)
               {
                   newHead = tail = cur;
                }
                else
                {
                  tail->next =cur;
                   tail = tail->next;
               }
              cur = cur->next;
            }
            else
            {
                struct ListNode* next = cur->next;
                free(cur);
                cur = next;
            }
        }
        if(tail)
            tail->next = NULL;
        return newHead;
}

画图解析:

二、分享：OJ调试技巧

LeetCode在线调试功能需要付费，我们可以自己在编辑器进行调试，写个模板，每次用到复制过去直接调试即可


int main()
{
    struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
    n1->val = 7;
    n2->val = 7;
    n3->val = 7;
    n4->val = 7;
    n5->val = 7;
    n1->next = n2;
    n2->next = n3;
    n3->next = n4;
    n4->next = NULL;
    removeElements(n1,7);
}

三、链表的中间结点

示例 1：

输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。

示例 2：

输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

提示：

链表的结点数范围是 [1, 100]
1 <= Node.val <= 100

代码解析：

此题我们学会了快慢指针


struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* slow,* fast;
    slow = fast = head;
    while(fast && fast->next)//节点为单数或者双数时出现的条件
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

画图解析：

四、链表中倒数第k个结点

输入一个链表，输出该链表中倒数第k个结点。

实例：

输入：1,{1,2,3,4,5}
返回值：{5}

代码解析：

此题依旧使用快慢指针

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    if(pListHead == NULL)
    {
        return NULL;
    }
    struct ListNode* slow,* fast;
    slow = fast = pListHead;

    //fast
    while(k--)
    {
        if(fast == NULL)
        {
            return NULL;
        }
        fast = fast->next;
    
    }
    while(fast)
    {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

画图解析：