反向双链切片列表 [英] reverse double linked cilcurar list

问题描述

假设我们有两个双键循环列表。我们想在O（1）中逆转他们。然后我们想要能够写这样的字母。 （O（n）（以相反的顺序，因为它们是相反的）。很容易，但是我们必须能够将这些列表组合成一个并写入它们。让我举几个例子：

让我们假设你有两个输入列表：可以操作：
join（示例显示它是如何工作的），显示和反向：
OK ：
第一个例子：

  L1：abcde 
 L2：fghij 
显示L1 ：abcde 
加入L1 L2（将第二个附加到第一个的结尾）
显示L1：abcdefghij 
反向L1（反向）
显示L1：jihgfedcba 
  

第二个：

  L1 abc 
 L2 def 
 L3 w 
反向L1 
加入L1 L2 
显示L1：cbadef 
加入L1 L3：
显示L1：cbadefw 
  

连接和反向的时间复杂度为O（1）

解决方案

使用一个附加参数直接转换循环双链表： order

双重链接列表的每个节点都有两个指针：向前和向后

• 如果订单为1，我们认为前进是指向
  的指针next元素


• 如果订单为-1，则我们认为向后是指向
  下一个元素的指针

我们也跟踪链表的end_point和start_point。颠倒列表基本上是交换start_point和end_point并颠倒顺序

  order = -1 * order 
 tmp = start_point 
 start_point = end_point 
 end_point = tmp 
  

合并列表与合并通常的双链表，但你必须考虑到订单。您基本上有3种情况可以处理：

1. 两者都向前移动


2. / li>
   
3. 一个正在前进，而另一个正在向后移动

Suppose we have two double-bonded cyclic list. We would like reverse them in O (1). Then we want to be able to write such letters. (O (n) (in reverse order, because they were reversed). Would be easy, but we have to be able to combine these lists into one and write in them. Let me give a few examples:

Let's say that you have two list on input. There are avaible to "operations": join ( the example show how it works), display and reverse: OK: First example:

L1: a b c d e 
L2: f g h i j 
Display L1 ( result: )  a b c d e
Join L1 L2 ( attach the second to the end of the first) 
Display L1 :  a b c d e f g h i  j
Reverse L1 ( reversing )
Display L1 : j i h g f e d c b a 

And second:

L1 a b c 
L2 d e f 
L3 w
Reverse L1
Join L1 L2
Display L1: c b a d e f 
Join L1 L3:
Display L1 : c b a d e f w

Time complexity for join and reverse is O(1), for Display is obviously O(n).

解决方案

Reversing a cyclic double linked list is straight forward using one additional parameter: order

Each node of a double linked list has two pointers: forward and backward

• if order is 1, we consider forward to be the pointer to the next element
• if order is -1, we consider backward to be the pointer to the next element

We also keep track of the end_point and the start_point of the linked list. Reversing the list is basically swapping start_point and end_point and reversing order

order = -1 * order
tmp = start_point 
start_point  = end_point
end_point = tmp

Merging the lists is not different from merging usual double linked lists, but you have to take into account the order. You basically have 3 cases to handle:

1. both are moving forward
2. both are moving backward
3. one is moving forward while the other is moving backward

这篇关于反向双链切片列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！