逆转交替合并两个链表的解析与实现

逆转交替合并两个链表，即从一个链表的尾指针指向另一个链表的尾指针，依次逆转交替进行合并。下面就通过实例来详细的介绍该逆转交替合并两个链表的思路与实现代码。

一、问题描述

链表A和B
A: 1->2->3->4
B: a->b->c->d
请逆转交替合并两个链表，示例结果如下：
4->d->3->c->2->b->1->a
节点类型定义如下:

classNode {
 public Node next;
 ...
}

二、源代码：

传入两个A和B链表，返回处理后的链表：


Node reverse_merge(Node A, Node B)
{
 //A、B都只有一个节点
 if(A.next==null)
 {
 A.next=B;
 return A;
 }
 //A、B都大于等于2个节点
 Node nextA;
 Node nextB; 

 nextB = B.next;
 B.next = null;
 nextA = A.next;
 A.next = B;
 B = nextB;
 while (nextA.next != null)
 {
 B.next = A;
 A = nextA;
 nextA = A.next;
 A.next = B;
 B = nextB;
 }
 nextB.next = A;
 nextA.next = B;
 return nextA;
}

三、解析：

程序分成三个部分——while循环之前、while循环体、while循环之后。
1）处理之前的链表A和B

2）while循环——核心的处理部分
这里处理程序的可重复的部分，我们的目标是红色的部分，要达成红色的链接模式，有两个原子结构：深红色圆圈1和蓝色圆圈2

但是1中需要特别处理a所在的节点，仅对于a所在的节点需要一个next=null的操作，也就是说1中的第一个原子要放在循环之外实现，这包括1指向a，b指向1的操作。

换种方式，如果使用2方式，就只需要将1指向a放在循环之外。所以，这里采用了2中描述的原子结构。

原子结构需要的信息

当我们进行到某一次循环时，假设进行到蓝色圆圈的操作了，这时候我们链表的状态为：

更为直观的画法为：

它涉及到3个节点——2,3和c。其中红色部分是我们希望做到的链接方式。为了链接c->2,3->c，必须知道有相应的指针记录他们的位置。所以在循环之前我们需要掌握这三个元素的地址，并且在处理完之后，用相同的方式表示下一次需要处理的原子结构。

例如以下这种方式记录这次循环中设计的3个节点的地址：

A、nA、B代表指向相应节点的指针或者说是引用。

在处理完成之后需要用相同的方式记录下一次原子结构涉及的节点，这样才能保证循环能够按统一逻辑执行下去，我们的目标是：

这些赋值操作正是循环体的中代码所做的事情，恰好代码也是按照上面指定的命名形式，有一点区别，图中的nA代表代码中的nextA。除此之外，代码中定义了nextB作为一个中间变量，用来记录c->d断开之前d节点的地址，因为c指向2之后就会失去对d的联系，这个中间变量是必须的。

3）while循环之前——解决预备操作所带来的问题

我们还没有处理a节点，因为它太特殊了，没有合适的原子结构能包括它。所以我们把它放在循环体之外，并且为循环做好准备工作，我们希望的结果是这样：

在这之后我们就可以把1，2，b放在循环体中处理。这里也考虑了A、B都只有一个节点的情况，也需要单独处理。

4）while循环之后——最后的处理

当我们发现B链表到达末尾时，结束循环。但这时候并有处理末尾节点，换句话说，末尾节点不在原子结构中。我们的循环会停止在这个原子结构中：

作为最后的操作，我们需要手动处理d->3,4->d的链接步骤——这也是没有办法的，因为原子结构的处理必须找到能够把所有指针传递下去的节点，作为最后的节点是没办法吧指针继续传递下去。

这不是一个完整的方法，还有很多事情没有处理，比如输入的A、B如果不等长，应该如何处理。另外Node数据结构并没有完整的定义，不过这都不是本文讨论的重点。

通过以上详细的解析，希望能够帮助大家很好的理解该逆转交替合并两个链表的方法与实现。

赞 (0)

相关推荐

  • Java采用循环链表结构求解约瑟夫问题

    本文实例讲述了Java采用循环链表结构求解约瑟夫问题的方法.分享给大家供大家参考.具体分析如下: 这是第一次java考试的试题,对于没看过链表的同学来说就不会做,现在回头看看,还真不难. 约瑟夫问题: 有n个人,其编号分别为1,2,3,-,n.这n个人按顺序排成一个圈.现在给定s和d,从第s个人开始从1依次报数,数到d的人出列,然后又从下一个人开始又从1开始依次报数,数到d的人又出列,如此循环,直到最后所有人出列为止.要求定义一个节点类,采用循环链表结构求解约瑟夫问题. 以下java版的答案:

  • C++语言实现线性表之链表实例

    本文实例讲述了C++语言实现线性表之链表实现方法.分享给大家供大家参考.具体分析如下: 插入.删除结点的代码有点多,但这样提高了代码的可读性,且不增加时间复杂度,不会影响程序性能 #include <iostream> using namespace std; template<typename T> class CList; template<class T> class Node { friend CList<T>; private: T m_data;

  • C#通过链表实现队列的方法

    本文实例讲述了C#通过链表实现队列的方法.分享给大家供大家参考.具体实现方法如下: public class Node { public int Data { get; set; } public Node Next { get; set; } public Node(int data) { this.Data = data; } } public class Queue { private Node _head; private Node _tail; private int _count =

  • C语言实现双向链表

    C语言实现双向链表

    这个小代码是我凭自己对指针和链表的理解和认识,自己实现的,没有参考其他人的代码,如果有相同的地方,那真的只是巧合,代码我在ubuntu 15.04下测试通过,可能存在很多错误和漏洞． doublelist.c /************************************************************************* > File Name: doublelist.c > Author: ChenYiLiang > Mail: chenyilian

  • 探讨:将两个链表非降序合并为一个链表并依然有序的实现方法

    已知两个链表list1和list,2,各自非降序排列,将它们合并成另外一个链表list3,并且依然有序,要求保留所有节点.实现过程中,list1中的节点和list2中的节点都转移到了list3中,注意泛型的友元函数的用法.程序如有不足之处,还望指正!!!定义List类 复制代码 代码如下: #include "stdafx.h"#include <iostream> using namespace std;template<class T>struct Node

  • JavaScript中数据结构与算法(三)：链表

    JavaScript中数据结构与算法(三)：链表

    我们可以看到在javascript概念中的队列与栈都是一种特殊的线性表的结构,也是一种比较简单的基于数组的顺序存储结构.由于javascript的解释器针对数组都做了直接的优化,不会存在在很多编程语言中数组固定长度的问题(当数组填满后再添加就比较困难了,包括添加删除,都是需要把数组中所有的元素全部都变换位置的,javascript的的数组确实直接给优化好了,如push,pop,shift,unshift,split方法等等-) 线性表的顺序存储结构,最大的缺点就是改变其中一个元素的排列时都会引起

  • JavaScript实现的链表数据结构实例

    此例是javascript来建立链表.. 并对此进行了排序.. 还可以在GenericList一般链表上进行扩展. 实现各种排序及增,删,改结点.. 复制代码 代码如下: function Node(){   this.data=null;   this.next=null; } function GenericList(){   this.head=null;   this.current=null;   //打出所有的链表结点   this.print= function(){   this

  • C++实现的链表类实例

    本文实例讲述了C++实现的链表类.分享给大家供大家参考.具体如下: #include <iostream> using namespace std; class linklist { private: struct node { int data; node *link; }*p; public: linklist(); void append( int num ); void add_as_first( int num ); void addafter( int c, int num );

  • 逆转交替合并两个链表的解析与实现

    逆转交替合并两个链表的解析与实现

    逆转交替合并两个链表,即从一个链表的尾指针指向另一个链表的尾指针,依次逆转交替进行合并.下面就通过实例来详细的介绍该逆转交替合并两个链表的思路与实现代码. 一.问题描述 链表A和B A: 1->2->3->4 B: a->b->c->d 请逆转交替合并两个链表,示例结果如下: 4->d->3->c->2->b->1->a 节点类型定义如下: classNode { public Node next; ... } 二.源代码: 传

  • PHP实现合并两个排序链表的方法

    本文实例讲述了PHP实现合并两个排序链表的方法.分享给大家供大家参考,具体如下: 问题 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则. 解决思路 简单的合并排序.由于两个数列本来就是递增的,所以每次将两个数列中较小的部分拿过来就可以了. 实现代码 <?php /*class ListNode{ var $val; var $next = NULL; function __construct($x){ $this->val = $x; } }*/ f

  • C语言合并两个带头节点升序排列链表

    合并链表,顾名思义,就是将两个按顺序存放数据的链表中的数据合并为用一个链表存储,比如在处理多项式的加减法时就需要将两个多项式的数据进行合并.合并方式有很多种:如果按照存储方式的不同,可以将两个链表的数据分别提取出来生成一个新的链表来存储原先两个链表的数据,还可以将其中一个链表的数据依次插入到另外一个链表的相应位置当中去.在遇到相同数据时可以采取只留下一个数据的方式和两个数据均保留的方式.这些不同点需要到具体的问题中具体分析,但是只是在细节上有一些差别,大体的思路都是一样的,本文主要介绍将一个链表

  • C++实现合并两个排序的链表

    本文实例为大家分享了C++合并两个排序的链表,供大家参考,具体内容如下 问题描述 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则. struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; 方法一 class Solution { public: ListNode* Merge(ListNode* pHead1, ListN

  • python实现合并两个排序的链表

    剑指offer:合并两个排序的链表,Python实现 题目描述 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则. 吐槽 本来想用递归实现,但是大脑卡壳,没有想到合适的递归策略,潜意识里还是把两个链表当成两个数组来看待,写出了非递归版本的代码.写完后回看自己写的代码,逻辑不够一目了然,中间变量过多,代码过长,一定不是好代码.上网查阅,发现一个如此美妙的递归版本,哇,写的好美啊!!!看来我对递归的了解和灵活应用还不够啊,至少在链表上还不够啊!!! 解题思路

  • Python实现合并两个有序链表的方法示例

    Python实现合并两个有序链表的方法示例

    本文实例讲述了Python实现合并两个有序链表的方法.分享给大家供大家参考,具体如下: 思路:先选出第一个节点,然后遍历两个链表,把小的作为当前节点的下一个节点,一直到其中一个链表遍历完,这时候把另一个链表直接接上就好 # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(obj

  • 对python实现合并两个排序链表的方法详解

    输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则. 1.迭代方法 def Merge(self, pHead1, pHead2): p1, p2 = pHead1, pHead2 if p1 and p2: if p1.val < p2.val: head = p1 p1 = p1.next else: head = p2 p2 = p2.next cur = head elif p1: return p1 else: return p2 while p

  • JS实现的合并两个有序链表算法示例

    JS实现的合并两个有序链表算法示例

    本文实例讲述了JS实现的合并两个有序链表算法.分享给大家供大家参考,具体如下: 将两个有序链表合并为一个新的有序链表并返回.新链表是通过拼接给定的两个链表的所有节点组成的. 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 可以直接运行的方案: <script> function Node(element) { this.element = element;//当前节点的元素 this.next = n

  • java编程题之合并两个排序的链表

    本文实例为大家分享了java合并两个排序的链表,供大家参考,具体内容如下 /** * * 剑指offer编程题(JAVA实现)--第16题:合并两个排序的链表 * * 输入两个单调递增的链表,输出两个链表合成后的链表, 当然我们需要合成后的链表满足单调不减规则. * */ public class Test16 { public static ListNode Merge(ListNode list1, ListNode list2) { if (list1 == null) { // 首先判断

随机推荐