逆转交替合并两个链表

发布时间:2017-09-07 14:42:57
逆转交替合并两个链表

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的链接步骤——这也是没有办法的,因为原子结构的处理必须找到能够把所有指针传递下去的节点,作为最后的节点是没办法吧指针继续传递下去。

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:武汉网页设计 https://www.feimao666.com

上一篇:DP hduHDU 5119
下一篇:最后一页