Contents

Linked List

Yue included in Algorithms

2022-03-27 231 words 2 minutes

Contents

Theory

Key points for using linked list:

when we are trying to dereference a ListNode, we should check if the node is null, or we may get an NPE (Null Pointer Exception).
We shouldn’t lose the control of head node, because if we lost it, we can not get the list’s nodes anymore. In some situations, like if we set a dummy, or trying to reverse a linkedlist, we may change the head, so it depends, but still need to be very careful.

Dummy Node: When we can not determine the head of linked list which we need to return, we may use dummy node.

Reverse Linked List

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


/** 
 * reverse (iteratively)
 */
public class Solution {
  public ListNode reverse(ListNode head) {
    // Write your solution here
    ListNode prev = null;
    while (head != null) {
      ListNode next = head.next;
      head.next = prev;
      prev = head;
      head = next;
    }
    return prev;
  }
}
/**
 * recursively
 */
public class Solution {
  public ListNode reverse(ListNode head) {
    // Write your solution here
    if (head == null || head.next == null) {
      return head;
    }
    ListNode newHead = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
  }
}

Online Algorithm