Find the 3rd last element in the Singly Link List - Algorithm

Question

I am thinking on the Algo to find the 3rd last element in the Singly Link List and I come up with one by myself(space in-efficient)
Put the Link List in a ArrayList using a loop with O(n)time complexity [a lot of space complexity]
then find the size of Arraylist and retrieve the element[required element] at (size-2) index location Please guide me if my algo make sense

FYI
Other I searched is : Put two pointers and keep 1st pointer on 1st element and 2nd pointer on 3rd element and move them parallel
When the second pointer reaches the end of LinkList, retrieve the node[required node] which is pointed by the 1st pointer

See: http://stackoverflow.com/questions/460137/algorithm-to-find-the-pointer-to-the-node-m-steps-to-tail-in-a-singly-linked-lis — maybeWeCouldStealAVan, Jul 05 '13 at 15:24
You can use a single pointer. Traverse until `ptr.next().next().next() == null`; — GriffeyDog, Jul 05 '13 at 15:35
@GriffeyDog Since a 'traversal' is series of `.next()` calls, you're doing three traversals, when only one is necessary. You method might be faster than three separate traversals, though, due to caching. — maybeWeCouldStealAVan, Jul 05 '13 at 15:46
@maybeWeCouldStealAVan It depends what the OP's goal is. I'm simply offering a _simply coded_ algorithm that maintains O(n) time complexity and adds no space requirements. I think the OP's second option would be just fine. — GriffeyDog, Jul 05 '13 at 16:05

Grijesh Chauhan · Accepted Answer · 2013-07-05T18:53:22.343

Use two pointers: pointer-1 and pointer-2

make pointer-1 points to third node in single linked list.

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

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

Now set pointer-2 points to first-node

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

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

Now, travel in linked list in a loop till pointer-1 points to last node, in loop also update pointer-2 (every time to next node of itself )

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

It works in O(n) times, where n is number of nodes in linked-list.

jh314 · Answer 2 · 2013-07-05T15:28:39.143

1

Since the linked list is singly linked, you need to traverse it from the beginning to end to know what the 3rd to last element is, os O(n) time is unavoidable (unless you maintain a pointer to the 3rd to last element in your linked list).

Your 2 pointers idea, will use constant space. This is probably the better option, since creating an ArrayList will have more overhead, and use more space.

edited Jul 05 '13 at 15:28

answered Jul 05 '13 at 15:21

jh314

27,144
16
62
82

Elbek · Answer 3 · 2013-07-05T15:29:45.557

0

Get two pointers. pA, pB Move pA to 3 elements advance and pB to the head:

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

After this, move both pointers in the same loop till pA reaches to the last element.

At that point pB will be pointing to the last 3rd element

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

Edited: traversal will be one:

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

Here pB will be 3rd last

edited Jul 05 '13 at 15:29

answered Jul 05 '13 at 15:23

Elbek

3,434
6
37
49

This would require two traversals. – maybeWeCouldStealAVan Jul 05 '13 at 15:25
1

one traversal, not two. You will move both pointers in one foreach – Elbek Jul 05 '13 at 15:25
That's still two traversals, done together. Better to hold three values, so that you don't need to traverse two pointers or traverse again to find the result. – maybeWeCouldStealAVan Jul 05 '13 at 15:30
A 'traversal' is a series of n 'next' operations. You're doing almost 2n (really 2n-2) of them. – maybeWeCouldStealAVan Jul 05 '13 at 15:43

score 0 · Answer 4 · answered Jul 05 '13 at 15:33

An alternative view to solve this even though it is O(n)

Create an empty array(n), start a pointer into this array at 0, and start from the beginning of the linked list as well. Every time you visit a node store it in the current index of the array and advance the array pointer. Keep filling the nodes in the array, and when you reach the end of the array please start from the beginning again so as to overwrite. Now once you end the final end of the list the pointer nth elemtn from end :)

maybeWeCouldStealAVan · Answer 5 · 2013-07-05T15:47:31.133

0

In practice, a Java LinkedList keeps track of its size, so you could just go to 'list.get(list.size()-2)', but with a constructed linked list, I'd do the following:

Keep an array of 3 values. As you traverse the list, add the update the value at array[i%3]. When there are no more values, return the value at array[(i-2)%3].

edited Jul 05 '13 at 15:47

answered Jul 05 '13 at 15:38

maybeWeCouldStealAVan

15,492
2
23
32

pjs · Answer 6 · 2013-07-05T16:14:06.973

The first thing I'd do is ask you to reconsider your use of a singly linked list. Why not just store your data in an ArrayList? It does everything you seem to want, and it's a builtin so it's relatively efficient compared to what most people would write.

If you were bound and determined to use a linked list, I'd suggest keeping a direct pointer to the 3rd last element (tle). Insertions are easy - if they come before the tle, do nothing; if after, advance the tle pointer to the tle's next. Removals are more of a hassle, but probably not most of the time. If the removal occurs before the tle, it's still the tle. The annoying situation is if the element to be removed is the tle or later, in which case you get to iterate through from the beginning until the next() reference of the current node is the tle. The current node will become the new tle, and you can then proceed with the removal. Since there are only three nodes which invoke this level of work, you'll probably do all right most of the time if the list is sizable.

A final option, if removals from the end are a frequent occurrence, is to maintain your list from back to front. Then the tle becomes the third from the front for maintenance purposes.

score 0 · Answer 7 · answered Aug 25 '14 at 13:12

    //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;
}

Find the 3rd last element in the Singly Link List - Algorithm

7 Answers7