逆置单链表、替换法之无头单链表的插入与删除

太过爱你忘了你带给我的痛 2022-05-12 08:48 266阅读 0赞

*   *   *   *  1. 从尾到头打印单链表
             *  2. 逆置单链表
             *  3. 删除一个无头单链表的非尾结点（不能遍历链表）
             *  4. 在无头单链表的一个结点前面插入一个结点（不能遍历）

#### 1. 从尾到头打印单链表 ####

我们知道，单链表只能够通过前面结点来找到后一个结点，不能直接通过后一个结点来找前一个结点，所以如何先打印后面的元素，在打印前面的元素。可以想到运用递归，设头结点为first  
第一次函数调用：first->next  
第二次函数调用：first->next->next  
第三次函数调用：first->next->next->next  
······  
······  
依次下去，然后倒着输出就可以了

void BackToFrontPrintRec(Node **ppfirst)
        {
            assert(ppfirst);
            assert(*ppfirst);
            Node *cur = *ppfirst;
            if (cur == NULL) 
            {
                return;
            }
            if (cur->next == NULL)
            {
                printf("%d ", cur->data);
                return;
            }
            BackToFrontPrintRec(&cur->next);
            printf("%d ", cur->data);
        }

那么不用递归又该如何输出尼？我们可以使用last指针，第一次让他指向NULL，第二次让他指向倒数第一个结点，第三次让他指向倒数第二个结点，依次类推，并将其数值打印即可

void BackToFrontPrint(Node **ppfirst)
        {
            assert(ppfirst);
            assert(*ppfirst);
            Node *last = NULL;
            Node *cur = *ppfirst;
            while (cur != last)
            {
                while (cur->next != last)
                {
                    cur = cur->next;
                }
                printf("%d ", cur->data);
                last = cur;
                cur = *ppfirst;
            }
        }

#### 2. 逆置单链表 ####

我们很容易想到在创建一个链表进行操作，定义一个result指针为空（作为逆置后的尾结点的next），只需要让原链表头删，然后在新链表头插即可  
![这里写图片描述][70]

void Reserve1(Node **ppfirst)
        {
            assert(ppfirst);
            assert(*ppfirst);
            Node *result = NULL;
            Node *cur = *ppfirst;
            Node *node = NULL;
            while (cur != NULL)
            {
                //上面头删
                node = cur;
                cur = cur->next;
                //下面头插
                node->next = result;
                result = node;
            }
        }

第二种方法和第一种方法思想实际上是一样的，但实现过程不一样，p1指向要移动的结点，p2指向p1的下一个结点，p1实际就是上一中方法的result  
![这里写图片描述][70 1]

void Reserve2(Node **ppfirst)
        {
            assert(ppfirst);
            assert(*ppfirst);
            Node *p1 = NULL;
            Node *p2 = *ppfirst;
            Node *p3 = p2->next;
            while (p2 != NULL)
            {
                p2->next = p1;
                p1 = p2;
                p2 = p3;
                if (p3 != NULL)
                {
                    p3 = p3->next;
                }
            }
        }

注：不管是哪种方法，都需要注意判断条件，可以只照三个结点，按照上述步骤操作一下，就知道判断条件怎样设置比较好，当然，判断条件不是唯一的

#### 3. 删除一个无头单链表的非尾结点（不能遍历链表） ####

我们只到，要删除一个结点，我们可以从头到尾找，然后删除。但这个不知道头结点，也就不能够开始遍历。这时候我们就要换一种思想——替换法，设要删除的结点为node，我们可以把node->next->data放在node->data中，然后让node指向node->next->next，这时候释放的是node->next，而不是node。  
![这里写图片描述][70 2]

void RemoveNoHeadNotTail(Node *node)
        {
            assert(node);
            Node *next = node->next;
            node->data = next->data;
            node->next = next->next;
            free(next);
        }

#### 4. 在无头单链表的一个结点前面插入一个结点（不能遍历） ####

这个和上一道题的思想是一样的，我们无法找到node结点的前一个结点，只能讲node和newNode里面的数据进行交换，然后再将newNode插入即可（交换之后，就要将newNode插入到node的后面而不是前面了）  
![这里写图片描述][70 3]

void InsertNoHeadNotTail(Node *node, DataType data)
        {
            assert(node);
            Node *newNode = CreateNewNode(data);
            newNode->data = node->data;
            newNode->next = node->next;
            node->data = data;
            node->next = newNode;
        }

注：替换法删除不能删除尾结点，替换法插入适用于任何结点。

[70]: /images/20220512/1a02d34f4dc240febda99b8e12654a3a.png
[70 1]: /images/20220512/27d8248efcb2421f870959f2f7003877.png
[70 2]: /images/20220512/a44d39467a0f4774b7e2dd25e1c735d2.png
[70 3]: /images/20220512/e4dff8592f3042518cdecb9bc987b6ed.png