LinkedList printMiddle method

Data Structures
1

In printMiddle method (in case of even number of elements)
Suppose there are 6 elements then the shared solution will give middle nodes as 4 & 5.
Correct answer should be 3 and 4… right??
Can anyone help me to understand if I am missing anything.

2

Hi,
I did not take that course. Can you provide more context ?
What language are you using to code printMiddle ?
Can you copy/paste the code here ?

Thanks.

3

For the record, this is a classic case of an underspecified problem statement. If the problem statement itself did not clarify what “the middle” is for an even number of elements (or what it should return for an edge case like an empty LinkedList) then in general that means you should either ask for clarification or just make a decision on your own.

Some possible answers for a LinkedList with 6 elements (let us suppose they are numbers, numbered by indices so 0, 1, 2, 3, 4, and 5):

  1. print both: 2, 3
  2. print the “first” middle: 2
  3. print the “last” middle: 3
  4. throw an exception saying “middle” is undefined for an even length list

Now getting back to your actual question:

As @UniqueNospaceShort asked, we need additional context. Given that I believe the data structures courses are based on Java (given other posts in the “Data Structures” category), but whatever language the course is in, the code should look pretty similar.

Given the answer you have suggested, I assume you must be working with LinkedList with the following elements: 1, 2, 3, 4, 5, 6. In which case it is pretty difficult to understand how “4 & 5” are the “middle” rather than “3 and 4” as you said. Although, perhaps you are misreading the code. Can you share the exact code we are dealing with?

4

Sorry for the confusion. Yes I am talking about finding middle element of LinkedList if we have even number of elements.
Here the code snippet that is shared in the course:

public void printMiddle() {
if (isEmpty())
throw new IllegalStateException();

var a = first; //here first is pointing to head of the LL
var b = first;
while (b != last && b.next != last) { //last is pointing to last element of LL
  b = b.next.next;
  a = a.next;
}

if (b == last)
  System.out.println(a.value);
else
  System.out.println(a.value + ", " + a.next.value);

}

1 Like
5

OK, let us walk through the application assuming that our nodes have the following definitions:

class Node {
  Node next;
  int value;
  Node(int value) { this.value = value; }
}

So basically the algorithm is you increment pointer a by 1 every iteration and pointer b by 2 every iteration. Once b reaches the end (or is 1 away from the end), we stop iterating and pointer a is at the “middle” (since it has advanced half as many steps through the linked list).

So going back to my example of having a linked list with elements 1, 2, 3, 4, 5, and 6, our structure looks like this:

Node first = new Node(1);
Node second = new Node(2);
first.next = second;
Node third = new Node(3);
second.next = third;
Node fourth = new Node(4);
third.next = fourth;
Node fifth = new Node(5);
fourth.next = fifth;
Node last = new Node(6);
fifth.next = last;

Then we start the iterations:

  1. a = first (1); b = first (1); now b != last (6) and b.next (2) != last so we start the loop
  2. b = b.next.next = 2.next = 3; a = a.next = 2; now b != last and b.next (4) != last so we continue the loop
  3. b = b.next.next = 4.next = 5; a = a.next = 3; now b != last, but b.next (6) == last, so we exit the loop
  4. b (5) != last (6) so we enter the else condition
  5. a.value (3) and a.next.value (4) are printed

That seems to print the expected 3 and 4 for the “middle” values. Is that not what you are seeing?

1 Like
6

Yes you are right… I made a mistake while implementing the code by myself.
Instead of iterating the loop till b.next != last, I was iterating it till b.next != null
That was causing the issue.

Thank you for the detailed explanation!

2 Likes