Linked List - Insert New Node

by LauCyun Aug 10,2014 16:45:49 6,929 views

数组在内存中是顺序存储的,要在数组中插入一个数据就变得颇为麻烦。这就像是在一排麻将中插入一个牌,必须把后面的牌全部依次顺移。然而,链表中各结点的关系是由指针决定的,所以在链表中插入结点要显得方便一些。这就像是把一条链子先一分为二,然后用一个环节再把它们连接起来。如图1所示。

图1

在建立的单链表中,插入节点有三种情况,如图2所示:

图2 单链表插入节点

插入的节点可以在表头、表中或表尾,以图3链表为例:

图3 单链表

1 表头插入节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

/***
 * Create a new node.
 * @param val: The value of the new node.
 * @return
 */
struct ListNode *newNode(const int val) {
    struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
    temp->val = val;
    temp->next = NULL;
    return temp;
}

/***
 * Insert a new node in the head of the linked list.
 * @param phead: The linked list of headers.
 * @param val: The value of the new node.
 * @return: The linked list of headers.
 */
struct ListNode * insertNewNodeInHead(struct ListNode * phead, const int val) {
    // init new node
    struct ListNode * new = newNode(val);

    if (phead == NULL) {
        phead = new;
    } else {
        new->next = phead;
        phead = new;
    }
    return phead;
}

新建立一个节点new,把new的后驱指针指向head,最后head的指针指向new

插入后,如图4所示:

图4 单链表表头插入节点

2 表中插入节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

/***
 * Create a new node.
 * @param val: The value of the new node.
 * @return
 */
struct ListNode *newNode(const int val) {
    struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
    temp->val = val;
    temp->next = NULL;
    return temp;
}

/***
 * Insert a new node in the any where of the linked list.
 * @param phead: The linked list of headers.
 * @param target: The value of the target node.
 * @param val: The value of the new node.
 * @return: The linked list of headers.
 */
struct ListNode * insertNewNodeInAnyWhere(struct ListNode * phead, const int target, const int val) {
    // init new node
    struct ListNode * new = newNode(val);

    if (phead == NULL) {
        phead = new;
    } else {
        struct ListNode * ptmp = phead;
        while (ptmp->next != NULL) {
            if (ptmp->val == target) {
                // The next pointer of the new node is equal to the next pointer to the current node.
                new->next = ptmp->next;
                // The next pointer of the current node is equal to the pointer to the new node.
                ptmp->next = new;
                break;
            }
            ptmp = ptmp->next;
        }
    }
    return phead;
}

新建立一个节点new,遍历找到target节点所在的位置ptmp,先把new的后驱指针指向ptmp的后驱指针,最后把ptmp的后驱指针指向new

插入后,如图5所示:

图5 单链表表中插入节点

3 表尾插入节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

/***
 * Create a new node.
 * @param val: The value of the new node.
 * @return
 */
struct ListNode *newNode(const int val) {
    struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
    temp->val = val;
    temp->next = NULL;
    return temp;
}

/***
 * Insert a new node in the tail of the linked list.
 * @param phead: The linked list of headers.
 * @param val: The value of the new node.
 * @return: The linked list of headers.
 */
struct ListNode * insertNewNodeInTail(struct ListNode * phead, const int val) {
    // init new node
    struct ListNode * new = newNode(val);

    if (phead == NULL) {
        phead = new;
    } else {
        struct ListNode * ptmp = phead;
        while (ptmp->next != NULL) {
            ptmp = ptmp->next;
        }
        // in tail
        ptmp->next = new;
    }
    return phead;
}

新建立一个节点new,移到链表尾部,将最后一个节点的后驱指针指向new

插入后,如图6所示:

图6 单链表表中插入节点

(全文完)

Tags