Posted on by Kalkicode
Code Single linked list

Insert a node at last nth position of linked list

In previous post mention about that, how to insert new created linked list node at beginning, middle position and end position of linked list. That is new problem, add new created node at nth last position in existing linked list. We can solve this problem in a two way.

First method : counting the all linked list nodes and check given position are valid or not. If position are valid ,then iterates by loop and find the ( counted node - given position ) node. And add a new node at that position. This methods are iterated loop in two times. time complexity is O(n).

Method 2: Use two pointers, And head pointer reference are assigned to both pointers. One pointer are used to iterates the linked list element is one by one and visited to next upcoming node.

And given position are decrement one by one. when position value are have 0 that meas given position are valid to situation and stopped the decrement position value. But first pointer are continue to visit. And respect to first pointer start moving on second pointer one by one until the first pointer are not NULL. If first pointer are NULL then add new element after that second pointer. This process only one loop are used to check valid position and inserted node to valid position. That is better approach as compare to first method.

In this post are implementing of the second approach. Suppose we are inserted the following (5, 4, 3, 2, 1) node in a sequence.

linked list before insert nth last position linked list after insert nth last position

Consider following test cases before write your code.

1) When linked list empty so in this case never find nth last node. So simple display empty linked list. You are also modified this test case when inserted position are 0 and adding new element to front of linked list. But we are assume that given position are always positive (more than zero).

2) When given position are one and linked list are not empty in this situation add new node to end of linked list. For example.

Linked list :   5  4  3  2  1 -->NULL
// position = 1 , data=10
After add   :   5  4  3  2  1  10 -->NULL

3) When total number of linked list node +1 are given position value then in this case add element at beginning of linked list.

Linked list :   5  4  3  2  1 -->NULL
// position = 6 , data=10
After add   :  10  5  4  3  2  1-->NULL

4) When given position more greater than (total node+1) In this situation not insert new node.

Here given code implementation process.


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment