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:

.. code-block:: none

  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

.. code-block:: c++

  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

.. code-block:: c++

  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

.. code-block:: c++

  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:

.. code-block:: c++

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


.. toctree::
   :maxdepth: 2

   questions