单链表常见算法题解

Code小燕儿 2021-09-01

377

hello，大家好，本文在上文单链表的基础上，继续探讨单链表的一些常见算法题，同样，本文所用语言为C语言，话不多说，开讲吧！

删除链表的倒数第N个节点

此题为LeetCode算法第19题，可采用双指针算法求解，同时引入虚拟头节点简化边界处理，具体代码及算法描述如下：

struct LinkList{
    int val;
    struct LinkList *next;
};


void removeNthFromEnd(struct LinkList **head, int N){
    // 定义虚拟头节点方便边界处理
    struct LinkList *dummy = (struct LinkList *)malloc(sizeof(struct LinkList));
    if(dummy == NULL){
        printf("哦豁，内存分配失败辽...\n");
        exit(1);
    }
    dummy->val = -1;
    dummy->next = *head;
    
    // 定义双指针
    struct LinkList *pre = dummy;
    struct LinkList *cur = *head;
    
    // cur指针先走 N个节点，此时cur与 pre之间间隔 N个节点
    for(int i = 0; i < N; ++i){
        cur = cur->next;
    }
    
    // 同步移动双指针直到cur指针到达单链表尾节点
    while(cur != NULL){
        cur = cur->next;  // 循环退出时cur指向NULL
        pre = pre->next;  // 循环退出时pre指向倒数第 N+1个节点
    }
    
    // 删除倒数第N个节点，释放堆空间
    struct LinkList *temp = pre->next;
    pre->next = pre->next->next;
    *head = dummy->next;
    free(dummy);
    free(temp);
}

上述程序的运行结果如下：

两两交换链表节点

此题为LeetCode算法第24题，涉及到多个链表指针操作时，苦思冥想一小时不如纸上画图两分钟来得快，同样此题定义虚拟头节点，每次让虚拟头节点移动两个节点的位置，直到链表结束或者剩一个节点为止，下图为此题算法思路示意

代码如下

void swapPairsLinkList(struct LinkList **head){
    // 定义虚拟头节点方便边界处理
    struct LinkList *dummy = (struct LinkList *)malloc(sizeof(struct LinkList));
    if(dummy == NULL){
        printf("哦豁，内存分配失败辽...\n");
        exit(1);
    }
    dummy->val = -1;
    dummy->next = *head;
    
    struct LinkList *cur = dummy;
    while(cur->next && cur->next->next){
        // 定义cur的后两个节点
        struct LinkList *node1 = cur->next;
        struct LinkList *node2 = cur->next->next;
        // 交换cur节点的后两个节点
        cur->next = node2;
        node1->next = node2->next;
        node2->next = node1;
        // 一次移动两个节点位置
        cur = node1;
    }
    *head = dummy->next;
    free(dummy);
}

上述代码的运行结果如下：

K个一组反转链表

此题为LeetCode算法第25题，算法思路如下：

特殊情况优先处理：链表为空、链表只有一个节点、k==1
计算链表长度，若链表长度小于k，直接返回即可
翻转k个链表节点（参考翻转单链表中反转链表部分，经典三指针翻转）
链接翻转前后的指针，递归进行下一次翻转

下图为上述算法思路示意图

上述算法的代码如下：

struct LinkList *reverseKGroup(struct LinkList **head, int k){
    // 特殊情况首先处理
    if(*head == NULL || (*head)->next == NULL || k == 1)
        return *head;
    // 计算链表长度
    int len = 0;
    struct LinkList cur = *head;
    while(cur != NULL){
        len ++;
        cur = cur->next;
    }
    // 若链表长度小于k,直接返回链表
    if(k > len) return *head;
    
    cur = *head;
    struct LinkList *node1 = NULL, *node2 = *head;
    // K个一组进行翻转，常规三指针法
    for(int i = 0; i < k; ++i){
        struct LinkList *temp = node2->next;
        node2->next = node1;
        node1 = node2, node2 = temp;
    }
    // K个一组翻转后，node2为下一组待翻转的头节点
    // node1为已翻转组的头节点
    // 链接翻转后的链表，递归进行下一次翻转
    cur->next = reverseKGroup(&node2, k);
    
    return node1;
}

上述代码的运行结果如下

删除链表重复元素Ⅰ

此题为LeetCode算法第83题，可通过一次遍历，若下一节点数值等于当前节点数值，直接跳过下一节点即可，代码如下：

void deleteDuplicates1(struct LinkList **head){
    if(*head == NULL || (*head)->next == NULL) return ;
    struct LinkList *cur = *head;
    while(cur->next){
        // 若节点值重复 则跳过下一节点
        if(cur->val == cur->next->val){
            cur->next = cur->next->next;
        }else{
            cur = cur->next;
        }
    }
}

上述代码的运行结果如下：

删除链表重复元素Ⅱ

此题为LeetCode算法第82题，与上一题不同的是，需要将重复元素斩草除根，由于头节点也可能被删除，因此引入虚拟头节点方便处理，代码如下：

void deleteDuplicates2(struct LinkList **head){
    // 特殊情况优先处理
    if(*head == NULL || (*head)->next == NULL) return ;
    // 创建虚拟头节点，方便头节点重复的处理
    struct LinkList *dummy = (struct LinkList *)malloc(sizeof(struct LinkList));
    if(dummy == NULL){
        printf("哦豁，内存分配失败了,,,\n");
        exit(1);
    }
    dummy->val = 0;
    dummy->next = *head;
    
    struct LinkList *cur = dummy;
    while(cur->next && cur->next->next){
        // 遇到重复节点
        if(cur->next->val == cur->next->next->val){
            int num = cur->next->val;
            // 循环跳过所有重复节点
            while(cur->next && cur->next->val == num){
                cur->next = cur->next->next;
            }
        }else{
            cur = cur->next;
        }
    }
    *head = dummy->next;
    free(dummy);
}

下图为上述程序运行结果

单链表插入排序

本题为LeetCode算法第147题，单链表插入排序算法与数组一致，从前往后遍历链表节点，将每一个节点插入到链表的合适位置即可，下图为算法示意图

上述算法思路代码如下：

void insertionSort(struct LinkList **head){
    if(*head == NULL || (*head)->next == NULL) return ;
    struct LinkList *dummy = (struct LinkList *)malloc(sizeof(struct LinkList));
    if(dummy == NULL){
        printf("哦豁，内存分配失败辽...\n");
        exit(1);
    }
    dummy->val = 0;
    dummy->next = NULL;
    
    struct LinkList *cur = *head;
    struct LinkList *pre = dummy;
    while(cur){
        // 循环退出时，pre指向插入位置的上一节点
        while(pre->next && pre->next->val <= cur->next){
            pre = pre->next;
        }
        // 将cur节点插入到 pre节点后面
        struct LinkList *temp = cur->next;
        cur->next = pre->next;
        pre->next = cur;
        // 每次插入完毕后，更近pre，方便下一次节点的插入
        pre = dummy;
        // cur指向下一个插入节点
        cur = temp;
    }
    
    *head = dummy->next;
    free(dummy);
}

上述代码的运行结果如下：

后记

分析上述算法题，可以发现处理链表题的一些技巧：

定义虚拟头节点方便边界处理
画图分析链表结构，否则很容易导致指针指向混乱
将当前处理节点、上一节点以及下一节点定义出来，方便指针分析

讲完啦，才发现新申请的公众号并没有留言功能，欢迎大家勘误或提出有效建议（邮箱号：seuhyz@163.com），欢迎大家分享转发，谢谢大家！

数据库

文章转载自Code小燕儿，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

单链表常见算法题解

评论