2.3. Linked List

As a data structure, linked list can be considered as a one dimension, simplified and flattened binary tree.

We will use this naming conversion in this chapter unless there is special declaration:

d - dummy node
c - current node, used to loop through the list
h - head of linked list
p - previous node
n - next node
nn - next next node
t - tmp node

  • Reverse a linked list

ListNode *p = NULL, *c = head, *n;
while (c) n = c->next, c->next = p, p = c, c = n;
// p is the new head now!

This kind of in-place chaining assignment is a pattern. It appears in many places like Rotating Image.

  • Find lower median of a linked list

ListNode* fast = head, *slow = head;
while (fast && fast->next && fast->next->next)
  fast = fast->next->next, slow = slow->next;
// slow is the lower median now!

  • Delete current node

p->next = c->next;
// p doesn't have to move

If there is no previous node p, we can copy next node to current node like:

// assuimg val and next are the only two member variables of the node
c->val=c->next->val, c->next=c->next->next;