list - 打印链表的第二个三分之一

Question

有 n 个节点的列表。

我必须编写一个伪代码，使用 3 个指针打印列表第二个三分之一的节点。复杂性是什么？

如果我可以通过柜台使用，这很容易，但这是被禁止的。

我想把前三个节点的三个指针放上去，然后拿到第三个指针旁边。如果它不是结束节点，请在第二个节点旁边。但我的伪代码太长太复杂。

另一个问题：我怎样才能通过使用两个指针来做到这一点？

例如：列表：1->2->3->4->5->6->7->8->9 灵魂打印元素：4,5,6。

任何帮助表示赞赏！

Answer 1

使用 2 个指针很容易：将指针 1 放在第 1 个位置，将指针 2 放在第 3 个位置

并做：

while pointer2 not null{
print pointer1
pointer1.next
print pointer1
pointer1.next
pointer2.next 3 times if pointer2 is not null
}

例如，列表是 1, 2, 3, 4, 5, 6

pointer1=1
pointer2=3

pointer2/=null then
print pointer1 (1)
pointer1.next
print pointer1 (2)
pointer1.next
pointer2=pointer2.next 3 times then pointer2=6

再次

pointer2/null then
print pointer1 (3)
pointer1.next
print pointer1 (4)
pointer1.next
pointer2.next is null, then the program will terminate here

你得到的列表是 1,2,3,4，它是 6 元素列表的 2/3

任何疑问都在这里回答:)

Answer 2

• 将所有指针设置为列表的头部。
• 虽然指针 3 不为空且其下一个不为空，但将指针 1 提前 1 个节点，将指针 2 提前 2 个节点，将指针 3 提前 3 个节点（当然，如果你到达终点，则停止）。
• 一旦 pointer3 到达列表的末尾，每个指针将是列表的 1/3，您可以打印它们之间的所有节点。

两个指针只是一个变体，但你写问题的方式有点模糊

列表的第二个三分之一的节点（2/3）

对我来说，“第二个三分之一”是指列表的中间三分之一，但你写了 2/3。

Answer 3

最后是两指针解，无计数器，无双链表

set the pointer1 in the 1st position
set the pointer2 in the 3rd position

while pointer2/=null{
pointer1.next
pointer2.next 3 times if pointer2=/null
}

//at this point we have the pointer1 in the first middle third element
//we only have to do the process again, but printing the elements
//we have to set the pointer2 to the third element, to start again

set the pointer2 in the 3rd position

while pointer2/=null{
pointer1.print
pointer1.next
pointer2.next 3 times if pointer2/=null
}

在第一次迭代中，我们将指针 1 放在中间三分之一的第一个元素中，在第二次迭代中，我们打印所有需要的元素，诀窍是指针 2 第一次到达末尾时重置

Answer 4

我找到了其他带有两个指针的解决方案，但链表必须是双链表（带有下一个和上一个）

set pointer 1 to the first element
set pointer 2 to the third element
while pointer 2/=null {
pointer1.next
pointer2.next 3 times if pointer2.next/=null
}
//in this part we have pointer1 in the first middle third element
while pointer1/=pointer2{
pointer1.next
pointer1.print
pointer2.prev
}

再次以 1,2,3,4,5,6 为例

pointer1=1
pointer2=3

pointer2.next/=null then
pointer1.next (pointer1=2)
pointer2.next 3 times, (pointer2=6)

pointer2.next=null then we enter in the second loop
pointer1.next  (pointer1=3)
pointer1.print (3)
pointer2.prev (pointer2=5)

pointer1/=pointer2 then
pointer1.next (pointer1=4)
pointer1.print(4)
pointer2.prev (pointer2=4)

pointer1==pointer2, end of program

我们在控制台输出中有 3,4