21xrx.com
2024-09-20 00:53:50 Friday
登录
文章检索 我的文章 写文章
C++实现有序链表合并
2023-07-05 04:21:27 深夜i     --     --
C++ 有序链表 合并

要实现有序链表合并，C++是一个非常好的工具。有序链表是一种常见的数据结构，在许多应用中都有广泛的应用。因此，当我们需要将两个有序链表合并成一个时，C++可以提供许多有用的工具和功能。

首先，我们需要定义一个结构体来表示链表节点。一个链表节点应该有一个指向下一个节点的指针和一个存储数据的字段。在这个示例中，我们假设链表节点的数据是整数。



struct Node {


  int data;


  Node* next;


};

接下来，我们需要实现一个函数来合并两个有序链表。在这个函数中，我们将遍历两个链表并将它们合并成一个新的有序链表。



Node* merge(Node* head1, Node* head2) {


  if (!head1)


    return head2;


  


  if (!head2)


    return head1;


  


  Node* cur1 = head1;


  Node* cur2 = head2;


  Node* result = nullptr;


  Node* tail = nullptr;


  if (cur1->data < cur2->data)


    result = cur1;


    cur1 = cur1->next;


   else


    result = cur2;


    cur2 = cur2->next;


  


  tail = result;


  while (cur1 && cur2) {


    if (cur1->data < cur2->data)


      tail->next = cur1;


      cur1 = cur1->next;


     else


      tail->next = cur2;


      cur2 = cur2->next;


    


    tail = tail->next;


  }


  if (cur1)


    tail->next = cur1;


  


  if (cur2)


    tail->next = cur2;


  


  return result;


}

在这个函数中，我们首先检查这些链表是不是空的。如果有一个链表为空，那么我们就返回另一个链表。否则，我们将首先找到较小值的节点，这将是新链表的头。然后，我们将遍历链表并将它们合并为一个新链表。

最后，我们将返回新链表的头节点。

这是如何使用这个函数的一个例子：



int main() {


  Node* head1 = new Node nullptr;


  Node* node1 = new Node nullptr;


  Node* node2 = new Node5;


  head1->next = node1;


  node1->next = node2;


  Node* head2 = new Node2;


  Node* node3 = new Node4;


  Node* node4 = new Node nullptr;


  head2->next = node3;


  node3->next = node4;


  Node* result = merge(head1, head2);


  Node* cur = result;


  while (cur)


    std::cout << cur->data << " ";


    cur = cur->next;


  


  std::cout << std::endl;


  return 0;


}

在这个例子中，我们定义了两个有序链表，并将它们合并成一个。我们最终得到了一个有序的链表，其中包含从1到6的编号。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复