WTF is ListNode??

I am just so frustrated with this ListNode concept in Leetcode so lemme arrange this notes.

Sample Solution

This is commented solution for Leetcode 19’s Remove Nth Node from end of list.

class Solution {
  public ListNode removeNthFromEnd(ListNode head, int n) {

    ListNode start = new ListNode(0);
    // 더미 노드 하나 생성
    ListNode front = start, back = start;
    // front와 back이라는 포인터 모두 0에 세팅
    start.next = head;
    // 더미 노드 뒤에 head 붙여주기
    // (head가 [1,2,3,4,5]라면 [0,1,2,3,4,5]가 된다)

    for(int i = 1; i <= n+1; i++){
      back = back.next;
    } // back이라는 포인트를 n번째 노드로 옮긴다

    while(back != null) {
      front = front.next;
      back = back.next;
    }
    // back이 null 될 때까지 n만큼의 간격을 유지하며
    // front와 back 포인터를 한칸씩 움직여준다

    // back이 null 됐을 때 = 리스트노드의 끝에 도달했을 때
    front.next = front.next.next;
    // front 포인터는 제외해야 하는 노드를 한 칸 건너뛴다.

    return start.next;
    // 더미 노드를 제외한 리스트노드를 반환한다.
  }
}

Definition of head in Leetcode’s ListNode

head is given as an array like [1,2,3,4,5] but it is marked as type ListNode. I am confused so is it ListNode of value 1 or the entire array?

You can either: link this head with a dummy node by dummy_node.next = head. So after your solution, when you return dummy_node.next (next because to skip the dummy node), the modified head is returned.

Or create a pointer right at the head. So for example, ListNode start = head means start points to ListNode of value 1.

How to approach question

1) Almost always, create a dummy node 2) We can’t use the length like an array cuz it is ListNode. Thus, use 2 pointers - 1 pointer reaches the end and becomes null and another pointer that is immobile when that other pointer is moved to create some distance between each other.