CODEWITHSUNDEEP
algorithmdata-structureslinked-list
Happydoodle Pa
Happydoodle Pa

Reputation: 81

A algorithm Question related to Linkedlist

I am trying to return middle node from a singly linkedlist here, and this is how I approach, but I keep getting Nullpointexception here. Can anybody explain where I am getting wrong?

 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
    ListNode slow = head; 
    ListNode fast = head;
        if (slow == null) {
            return null;
        }
        if (slow.next.next == null) {
            return slow.next;
        }
        while (slow.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

Upvotes: 0

Views: 74

Answers (1)

Ekesh Kumar
Ekesh Kumar

Reputation: 525

I believe that there is no error in this code.

I just ran your code with a Linked List that looks like 1->2->3->4->5, like you stated in the comments, and it works just fine.

Also, this is a question from LeetCode, and the code you posted passes all of the test cases on there. In fact, this code looks identical to the third solution that is provided on there (which you can see by clicking the "solution" tab).

Post-Edit:

The reason why you're getting a null pointer exception in your updated code is because you're not checking whether or not fast.next is null prior to accessing fast.next.next. Thus, if you change the while-loop condition from while (slow.next != null && fast.next.next != null) to while (slow.next != null && fast.next != null && fast.next.next != null), then you'll get rid of the null pointer exception.

However, this will still result in a verdict of Wrong Answer, because your algorithm is not correct.

You should not be checking whether fast.next and fast.next.next are non-null but instead, you should be checking whether fast and fast.next are null. I suggest you work it out on paper to see why (the code you posted will fail for 1->2->3->4->5->6, for which the answer should be ListNode 3). The updated code with these changes is provided below:

class Solution {
    public ListNode middleNode(ListNode head) {
    ListNode slow = head; 
    ListNode fast = head;
        if (slow == null) {
            return null;
        }

        if (slow.next == null) {
            return slow;
        }

        while (slow.next != null && fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

Upvotes: 1

Related Questions