构建有序链表，有序链表的归并，反转链表

本次将对于构建有序链表，有序链表的归并，反转链表，进行一一介绍和代码分享。

首先是一些链表中的基本的函数：

Node* creatList()
{
    Node* headNode = (Node*)malloc(sizeof(Node));
    assert(headNode);
    headNode->next = NULL;
    return headNode;
}
 
Node* creatNode(Datatype data)
{
    Node* newNode = (Node*)malloc(sizeof(Node));
    assert(newNode);
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}
 
void traverseList(Node* headNode)
{
    Node* posNode = headNode->next;
    while (posNode != NULL)
    {
        printf("%d ", posNode->data);
        posNode = posNode->next;
    }
}

这里很基本，如果理解有困难，请从头学习链表。

以下是构建有序链表，也就是找到符合顺序的位置进行节点插入：

//构建有序链表：和构建顺序表一样，需要找到符合顺序的位置，然后插入元素
//核心是找到第一个比它大的节点，放到这个节点之前（双节点遍历）
void insertData(Node* headNode, Datatype data)
{
    Node* newNode = creatNode(data);
    Node* posNode = headNode->next;
    Node* preNode = headNode;
    //assert(posNode);
    //当前面节点的数据小于data的时候，继续向后走
    while (posNode!= NULL && posNode->data <= data)
    {
        posNode = posNode->next;
        preNode = preNode->next;
    }
    //特殊的情况分析：(短路现象）
    //pos在第一个节点，第一个节点为空，那么说明只有表头,连接表头和newNode
    if (posNode == NULL&&posNode == headNode->next)
    {
        headNode->next= newNode;
    }
    //pos不在第一个节点，但是pos指向空，
    //pos指向最后一个节点的后面一个，也就是还有没有找到大于data的：
    // 说明没有大于data的节点，所以将data与最后连接即可
    else if (posNode == NULL && posNode != headNode->next)
    {
        preNode->next = newNode;
    }
    //找到了位置，插入在pos的前面
    else
    {
        newNode->next = posNode;
        preNode->next = newNode;
    }
}

这个过程和顺序表的构建流程基本相同，比较简单，所以不做过多解释。

接下来是单链表的翻转：

void reverseList(Node* headNode)
{
   //对于1个表头，1个节点；1个表头，2个节点的链表不需要进行翻转
   if (headNode->next == NULL || headNode->next->next == NULL)
   {
       return;
    }
    Node* posNode = headNode->next;
    Node* preNode = NULL;
    Node* sucNode = headNode->next->next;
    while (sucNode != NULL)
    {
        //指向改变
        posNode->next = preNode;
        //整体向后移动
        preNode = posNode;
        posNode = sucNode;
        sucNode = sucNode->next;
    }
    //最后一步改变指向方向
    posNode->next = preNode;
    //将表头与完成反转的第一个节点相连接
    headNode->next = posNode;
}

以下是逐步的过程模拟：结合代码中的注释和过程一一对应更容易理解，其中preNode，sucNode分别是posNode的前驱和后继节点。

示例

假设我们有以下的单链表：

我们希望反转后得到：

分析执行过程

1. 初始化指针：
   • posNode 指向第一个元素（1）。
   • preNode 为 NULL（因为没有前驱节点）。
   • sucNode 指向第二个元素（2）。
2. 进入循环，当 sucNode 不为 NULL 时：
   • 改变 posNode（当前节点）的 next 指针，使其指向前驱节点 preNode。
   • 更新 preNode 为当前的 posNode。
   • 更新 posNode 为当前的 sucNode。
   • 更新 sucNode 为 posNode 的下一个节点。

这个过程会一直持续到 sucNode 为 NULL，即到达链表的末尾。

1. 在循环结束后，执行以下操作：
   • 将最后一个节点（posNode）的 next 指针指向 preNode。
   • 将头节点的 next 指针指向反转后的第一个节点（posNode）。

最后，两个有序链表的归并：

//有序链表的归并：
void mergeList(Node* newHeadNode, Node* head1, Node* head2)
{
    Node* up = head1->next;
    Node* down = head2->next;
    Node* temp = newHeadNode;
    assert(up && down);
    while (up != NULL && down != NULL)
    {
        if (up->data < down->data)
        {
            temp->next= up;
            up = up->next;
        }
        else
        {
            temp->next = down;
            down = down->next;
        }
        temp = temp->next;
    }
    //up结尾，down没结尾
    if (up == NULL && down != NULL)
    {
        temp->next = down;
    }
    //down结尾，up没结尾
    else if (up != NULL && down == NULL)
    {
        temp->next = up;
    }
    //没有两个同时结尾的情况
}

示例和分析执行过程：

假设我们有以下两个有序链表：

调用 mergeList(newHeadNode, head1, head2); 后，我们希望得到以下合并后的链表：

执行过程：

1. up 指向 1，down 指向 2，temp 指向 newHeadNode。
2. 因为 1 < 2，所以 temp->next = up;，然后 up 移动到 3，temp 移动到 1。
3. 现在 up 指向 3，down 指向 2。
4. 因为 2 < 3，所以 temp->next = down;，然后 down 移动到 4，temp 移动到 2。
5. 重复这个过程，直到 up 或 down 为 NULL。
6. 在本例中，当 up 指向 5 且 down 指向 4 时，因为 4 < 5，down 指向的节点会被插入到新链表中。
7. 当 down 遍历到 NULL 时，up 还有节点 5 和 6。因此，将 up 指向的剩余链表直接连接到新链表的末尾。

对于链表的归并，代码虽然简单，但要理解其中的流程是极为关键的，本次的分享结束，希望对你有帮助。