玩链表

作者: 凉风起君子意如何 | 来源:发表于2022-08-15 13:59 被阅读0次

玩链表
scala 实现链表
链表基础
双向链表&双向循环链表
算法与数据结构:链表
链表
五、双向链表
链表
数据与算法结构
数据结构——链表

该文章主要讲述单链表的一些常用简单操作。包含如下功能：

创建头结点
根据值创建新节点
从终端读取链表（头插法和尾插法）
释放链表
打印链表
逆序链表-头插法
逆序链表-三指针变量法
合并两个升序链表
判断回文链表（快慢指针）
删除某个节点
删除链表中重复的节点

玩链表，不光是链表，好像跟指针相关，或者跟算法沾点关系的，似乎都应该画图，因为有时候你左思右想前看后看，最后都不如一张图来的直观，不管是自己画的草图也好还是大神做的精图也罢。

这里是Demo代码，玩玩就好。

废话不多说->正题

基本的操作，像定义节点、创建头结点、创建新节点、释放链表、打印链表等，这里就不过多说了，demo里都写的很清楚。以下主要看看关于单链表比较常用的一些操作：

新建链表（头插法）

头插法

结合上面的图再看如下的核心代码，确实很容易看懂

// 将新加的节点插入到链表中；头插法；return 0成功，return -1 失败
int add_node_head(Node* head, Node* new_node) {
    if (head == NULL || new_node == NULL) {
        return -1;
    }
    new_node->next = head->next;
    head->next = new_node;
    return 0;
}

判断回文链表（快慢指针法）

什么是回文？类似[1,2,2,1], [1,2,4,2,1] 这种以中间对称前后读或数都一样的一组数据。回文单链表是指链表中节点value值也符合这种规律。
思路：定义两个快慢指针，慢指针走一步，快指针走两步，当快指针走到尾的时候，慢指针正好走在链表中间，此时将链表后半部分逆序，最后再比较前半部分和逆序后的后半部分，看值是否都相同，若是则为回文链表。

判断回文链表草图
核心代码：

// 回文链表判断 快慢指针法
int isHuiwen(Node *head) {
    if (head == NULL || head->next == NULL) {
        printf("只有一个节点 是回文链表");
        return 1;
    }
    Node *slow = head;
    Node *fast = head;
    // 逆序后半部链表 变量定义
    Node *head1 = create_link_head(); // 注意这个赋值，不要直接=head
    Node *pre = NULL, *temp = NULL,*p = NULL;
    while (fast!=NULL && fast->next!= NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    p = slow->next;
    // 逆序后半部分链表 三个变量指针法
    while (p) {
        temp = p->next;
        p->next = pre;
        pre = p;
        p = temp;
    }
    // 注意是head1->next,不是head1。注意赋值的是pre不是 p，p此时已经是NULL了
    head1->next = pre;
    // 两链表依次比较值，看是否相同，若都相同则是回文链表，否则不是
    while ((head = head->next) !=NULL && (head1 = head1->next) !=NULL) {
        if (head->data != head1->data) {
            printf("不是回文链表\n");
            return 0;
        }
    }
    printf("是回文链表\n");
    return 1;
}

逆序链表（三指针变量法）

这里列出的是三指针变量法，其实也可以用上面的新建链表头插法。

逆序链表草图

草图上有代码，就不重复列举啦。或查看上面demo。

合并两个升序链表

合并两个升序列表草图

上图l1和l2分别是两个链表的头结点，l是用来跟踪新链表的当前位置。核心代码如下：

void callMyMergeLink() {
    Node *l1, *l2, *l;
    l1 = readLink();
    l2 = readLink();
    display_link(l1);
    display_link(l2);
    l = mergeLink(l1, l2);
    display_link(l);
}

Node *mergeLink(Node *l1,Node *l2) {
    Node *head, *l;
    head=l= (Node*)malloc(sizeof(Node));
    l->next = NULL;
    Node *p = l1->next,*s = l2->next;
    while (p != NULL && s!= NULL) {
        if (p->data <= s->data) {
            l->next = p;
            p = p->next;
            l = l->next;
        }else {
            l->next = s;
            s = s->next;
            l = l->next;
        }
    }
    if (p == NULL) {
        l->next = s;
    }
    if (s == NULL) {
        l->next = p;
    }
    l1->next = NULL;
    l2->next = NULL;
    return head;
}

删除链表中某个节点

注意点：如何记录要删除的前一个节点，及特殊情况第一个节点的处理

核心代码：

Node *deleteNode(Node *head, int val) {
    if (head == NULL || head->next == NULL) {
        return NULL;
    }
    Node *temp = head->next, *pre = head;
    // 第一个节点就是 要删除的节点
    if (temp->data == val) {
        head->next = temp->next;
        free(temp);
        return head;
    }
    while (temp!=NULL && pre!=NULL) {
        if (temp->data == val) {
            pre->next = temp->next;
            free(temp);
            break;
        }
        pre = temp;
        temp = temp->next;
    }
    return head;
}

该原题出处牛客网

删除链表中重复的节点

关键点：怎么删除连续的重复的节点，如下代码没有free掉重复的节点，只是丢弃了。若要释放重复的节点可以新建链表记录之后统一free掉

核心代码：

// 删除链表中重复的节点，例如1->2->3->3->5,删除重复的3节点之后 为1->2->5
Node *deleteDup(Node *head) {
    if (head == NULL || head->next == NULL) {
        return NULL;
    }
    Node *curr = head->next, *pre = head;
    while (curr->next!=NULL && pre!=NULL) {
        int temp = curr->data;
        if (curr->data == curr->next->data) { // 有相邻重复的
            while (curr->next != NULL && curr->next->data == temp) {
                curr->next = curr->next->next;
            }
            pre->next = curr->next;
        }else {
            pre = curr;
            curr = curr->next;
        }
    }
    return head;
}