1

我正在考虑在算法上找到单链接列表中的倒数第三个元素，我自己想出了一个（空间效率低）
使用具有 O(n) 时间复杂度的循环将链接列表放入 ArrayList [a很多空间复杂度]
然后找到Arraylist的大小并在（size-2）索引位置检索元素[必需元素]如果我的算法有意义，请指导我

仅供参考
我搜索的其他内容是：放置两个指针并将第一个指针保留在第一个元素上，将第二个指针保留在第三个元素上，并将它们平行移动
当第二个指针到达 LinkList 的末尾时，检索第一个指针指向的节点 [必需节点]

4

7 回答 7

6
  • 使用两个指针：pointer-1和pointer-2

  • pointer-1指向单链表中的第三个节点。 

     pointer-1 = node1->next->next; // point to 3rd nd

 node1-->node2-->node3-->node4---> ...... -->node-last
                 ^
                 |
                pointer-1

  • 现在将pointer-2点设置为第一个节点

     pointer-2 = node1;   // point to 1st nd

 node1-->node2-->node3-->node4---> ...... -->node-last
   ^              ^
   |              |
  pointer-2      pointer-1

  • 现在，在循环中的链表中旅行直到pointer-1指向最后一个节点，在循环中还更新指针2（每次到自身的下一个节点）

    while (pointer-1->next!=NULL){// points to last node 
     pointer-1 = pointer-1 -> next;
     pointer-2 = pointer-2 -> next;
}

When loop ends pointer-1 points to last-node, pointer-2 points to third last

 node1-->node2-->........ ->node-l3-->node-l2-->node-last
                             ^                   ^
                             |                   |
                           pointer-2            pointer-1

它的工作时间为 O(n) 次，其中n是链表中的节点数。

于 2013-07-05T15:26:03.350 回答
1

由于链表是单链的，你需要从头到尾遍历它才能知道倒数第三个元素是什么，操作系统O(n)时间是不可避免的（除非你维护一个指向链表中倒数第三个元素的指针）。

您的 2 指针想法将使用常量空间。这可能是更好的选择，因为创建 ArrayList 会产生更多开销，并使用更多空间。

于 2013-07-05T15:21:42.000 回答
0 
    //We take here two pointers pNode and qNode both initial points to head
    //pNode traverse till end of list and the qNode will only traverse when difference
   // between the count and position is grater than 0 and pthNode increments once
  // in each loop
    static ListNode nthNode(int pos){
    ListNode pNode=head;
    ListNode qNode=head;
    int count =0;
    while(qNode!=null){
        count++;
        if(count - pos > 0)
            pNode=pNode.next;
        qNode=qNode.next;
    }
    return pNode;
}
于 2014-08-25T13:12:54.130 回答
0

我要做的第一件事是要求您重新考虑使用单链表。为什么不将数据存储在 ArrayList 中？它可以完成您似乎想要的一切，而且它是内置的，因此与大多数人编写的相比，它相对高效。

如果您被绑定并决定使用链表，我建议您保留一个指向倒数第三个元素（tle）的直接指针。插入很容易——如果它们出现在 tle 之前，什么也不做；如果之后，将 tle 指针推进到 tle 的下一个。删除更麻烦，但可能不是大多数时候。如果删除发生在 tle 之前，它仍然是 tle。烦人的情况是，如果要删除的元素是 tle 或更高版本，在这种情况下，您可以从头开始迭代，直到当前节点的 next() 引用是 tle。当前节点将成为新文件，然后您可以继续删除。由于只有三个节点调用此级别的工作，因此如果列表相当大，您可能大部分时间都可以正常工作。

最后一个选项，如果从末尾删除经常发生，是从后到前维护您的列表。然后，出于维护目的，该 tle 变为从前数第三个。

于 2013-07-05T16:07:46.773 回答
0

在实践中，JavaLinkedList会跟踪它的大小，因此您可以直接转到“list.get(list.size()-2)”，但是使用构造的链表，我会执行以下操作：

保留一个包含 3 个值的数组。遍历列表时，将更新值添加到array[i%3]。当没有更多值时，返回 处的值array[(i-2)%3]。

于 2013-07-05T15:38:33.863 回答
0

得到两个指针。pA, pB 将 pA 移动到 3 个元素，将 pB 移动到头部：

1->2->3->4-> .... ->99->100 
|     |
pB    pA

之后，在同一个循环中移动两个指针，直到 pA 到达最后一个元素。

那时 pB 将指向最后的第三个元素

1->2->3->4-> .... ->98->99->100 
                    |        |
                    pB       pA

编辑：遍历将是一个：

while(pA->next!=null){
   pA = pA->next;
   pB = pB->next;
}

这里 pB 将是倒数第三

于 2013-07-05T15:23:16.757 回答
0

解决这个问题的另一种观点，即使它是 O(n)

创建一个空数组（n），从 0 开始指向该数组的指针，并从链表的开头开始。每次访问一个节点时，将其存储在数组的当前索引中并推进数组指针。继续填充数组中的节点，当到达数组末尾时，请重新从头开始，以便覆盖。现在，一旦您结束列表的最后一端，指针 nth elemtn from end :)

于 2013-07-05T15:33:27.740 回答