-1

I was implementing the "reverse single linked list, do it in-place" task. I came up with this solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }

        if(head.next==null) return head;

        ListNode n = head;
        ListNode r = null;
        ListNode temp = null;

        while (n != null) {
            temp = n;
            n = n.next;
            temp.next = r;
            r = temp;
        }

        return r;
    }
}

and it works:

1 2 3 4 5 
5 4 3 2 1

but when I wanted to make sure it's the right approach all the solutions I've seen online look like that Reverse single linked list so I started questioning myself... What is wrong with my solution? Time complexity looks like O(n) space com. O(1)... Am I wrong? Thanks in advance!

Community
  • 1
  • 1
grape
  • 89
  • 2
  • 8
  • 1
    Your solutions looks good to me!. I did a check against leetcode(https://leetcode.com/) and it passed all test cases just fine. Just because there are other more popular solution means your own solution is wrong. – MSameer May 04 '16 at 01:39
  • complexity must be at least the order of n, since you need to switch pointer direction for every node in the list – mangusta May 04 '16 at 01:40
  • I know that time compl must be O(n), but what about space? Does my solution fits the requirement of space compl O(1)? – grape May 04 '16 at 01:43
  • 1
    @grape yes, your space complexity is constant – mangusta May 04 '16 at 01:45

1 Answers1

0

Not sure what you are asking. Your implementation looks almost just like the one in the link. Both implementations are O(n) for time complexity, and O(1) for space complexity. Of course, the list itself is O(n) for space complexity.

Jai
  • 8,165
  • 2
  • 21
  • 52
  • Compare the solustions closely, I'm doing it in different order, and the order her might be tricky – grape May 04 '16 at 01:46
  • Actually I read yours first, and it made sense. Except that the variable names are... badly named XD I didn't read the link's one in detail, though. – Jai May 04 '16 at 01:48
  • Nevertheless, all you wanted to know is time/space complexity right? I realized I was confused by the phrasing of your last sentence of the question. – Jai May 04 '16 at 01:50