数据结构初阶leetcodeOJ题（二）

目录

第一题

 思路：

第二题

 思路

 第三题

描述

示例1

 思路

总结：这种类似的题，都是用快慢指针，相差一定的距离然后输出慢指针。

---

第一题

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

示例 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
输出：[]

 方法一

思路：

快慢指针：一个指向目标结点，一个指向目标结点的前驱结点。用一个tmp保存pos->next.

                  free()掉目标结点。

分两种情况：如果只有一个节点或者要删除的结点是首元节点，那么这时pre为NULL，pos                       指向pos；否则pre->next == pos；

 

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

方法二： 

思想；

创建新链表，用尾插法，尾插法没有改变原指针的next指向所以不用保存next节点，

但是在free（）时要保存下一节点。

 

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

 

 

第二题

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

如果有两个中间结点，则返回第二个中间结点。

示例 1：

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

示例 2：

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

 思路

用快慢指针：快指针一次走两个，慢指针一次走一个。这样他们的路程之间差二倍。所以输出慢指针，即输出中间节点。

 

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

 第三题

描述

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

示例1

输入：

1,{1,2,3,4,5}

复制返回值：

{5}

 思路

用快慢指针：快指针比慢指针先走k步，然后两者在同时走。

 

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    struct ListNode* pre =pListHead;
    struct ListNode* pos = pListHead;
    while(k--){
        if(pos!=NULL){
        pos = pos->next;
        }else{
            return NULL;
        }
 
    }
    while(pos!=NULL){
 
        pre = pre->next;
        pos = pos->next;
 
    }
    return pre;
 
}

总结：这种类似的题，都是用快慢指针，相差一定的距离然后输出慢指针。

第四题 

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

示例 1：

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

示例 2：

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

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

 方法一

 将节点之间的next翻转。

用三个指针的原因是，只用两个指针翻转时，会导致链表断裂，但是用第三个指针保存下一个节点这样链表就不会断裂。

 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 
 //方法一
struct ListNode* reverseList(struct ListNode* head) {
    if(head==NULL)
        return NULL;
    struct ListNode* left = NULL;
    struct ListNode* right= head;
    struct ListNode* tmp = head->next;
    while(right!=NULL)
    {
 
        right->next = left;
        left = right;
        right = tmp;
        if(tmp!=NULL)
        tmp = tmp->next;
    }
 
    return left;
}

方法二 

用头插法，注意头插法需要保存指针。尾插法不用保存指针。

错误总结

 

（1）注意头插是新结点指向头结点，然后在将新节点设置为头结点。而不是直接将新节点设置为头节点 

（2）C语言赋值语句，左值是变量，将新节点设置为头结点。newnode = cur；这是头结点为cur

 

//方法二
struct ListNode* reverseList(struct ListNode* head) 
{
   if(head==NULL)
        return NULL;
    struct ListNode* cur = head;
    struct ListNode* newhead = NULL;
    while(cur!=NULL)
    {
 
        struct ListNode* next = cur ->next; //保存下一个
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    return newhead;
}