提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

【拿捏链表（Ⅰ）】—作为程序员必须会的链表经典题目

程序员
2023-03-07 09:46:33 时间

目录

反转链表

题目：该题是力扣中的一道关于链表的简单经典题目。如下：

思路：我们可以这么来想，假如正常尾插1 2 3 4 5的话，链表就是当前的1->2->3->4->5->NULL,但是假如我们将1 2 3 4 5进行头插的话，就会变成：5->4->3->2->1->NULL。所以，这里我们采用头插法进行反转。原理如下图：

代码实现：

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode*cur=head;
    struct ListNode*prev=NULL;//新头节点
    //取节点头插
    while(cur!=NULL)
    {
        struct ListNode*Next=cur->next;//下一个节点
        cur->next=prev;
        prev=cur;
        cur=Next;
    }
    //返回新节点
    return prev;//假如是个空表，prev==NULL依然适用
}

链表中倒数第k个结点

思路：对于这道题，我们可能上来就会想到：先统计节点的个数n，然后再走n-k步，就可以走到倒数第k个位置，这个方法肯定是可行的。不过这里我要讲的是另一种思路：快慢指针法 即：我们可以定义fast与slow两个指针，fast指针先走k步，然后再让slow与fast同时走，当fast走到NULL时，slow就处在倒数第k个位置。如下：

代码实现：

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    struct ListNode*fast=pListHead;
    struct ListNode*slow=pListHead;
    //先走k步
    while(k--)
     {
         //空链表，或者k过大
        if(fast == NULL)
        {
            return NULL;
        }
        fast=fast->next;

    }
    //同时继续往后走，slow走了n-k步
    while(fast)
    {
        slow=slow->next;
        fast=fast->next;
    }
    //返回slow
    return slow;
}

删除链表中的节点

思路：这里我们需要注意，题目中明确说明node不是最后一个节点，并且也说了，只是让node节点的值不存在与这个链表，并且链表总结点-1.还要保持前后的值的顺序不变。 不要小看这些提示，它会使我们更容易入手。我们可以这么来搞：我们把node后面节点的值赋给node节点，然后让node指向它后面的后面的节点，最后再释放node的下一个节点。就可以保证以上所有要求！如下：

代码实现：

void deleteNode(struct ListNode* node) {
    struct ListNode*next=node->next;//记录node的下一个节点
    node->val=next->val;//赋值
    node->next=next->next;//node的下一个节点指向next的下一个节点
    free(next);//释放next
}

题目倒是挺长的，但理解后其实没啥，切记一定要多画图，有助于理解！

相关文章