LINKED LIST

链表

160. 相交链表

编写一个程序，找到两个单链表相交的起始节点。

例如，下面的两个链表：

  A:          a1 → a2
                     ↘
                       c1 → c2 → c3
                     ↗            
  B:     b1 → b2 → b3

在节点 c1 开始相交。

注意：

如果两个链表没有交点，返回 null. 在返回结果后，两个链表仍须保持原有的结构。 可假定整个链表结构中没有循环。 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

public ListNode GetIntersectionNode(ListNode headA, ListNode headB)
{
    if(headA == null || headB == null)
        return null;

    ListNode a = headA, b = headB;

    while(a != b)
    {
        a = a == null ? headB : a.next;
        b = b == null ? headA : b.next;
    }
    return a;
}

原理很简单，len(A + B) = len(B + A)，所以A链表接在B链表后面为链表1，B链表接在A链表后面为链表2，链表1和链表2的长度相同，同时开始遍历，定能找到相同的节点(如果不存在则循环停止在a == b == null)。（如果不理解的话就按上面的例子画一下试试）

328. 奇偶链表

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

示例 1:

输入: 1->2->3->4->5->NULL 输出: 1->3->5->2->4->NULL

示例 2:

输入: 2->1> ->3->5->6->4->7->NULL 输出: 2->3->6->7->1->5->4->NULL

说明:

应当保持奇数节点和偶数节点的相对顺序。 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

public ListNode OddEvenList(ListNode head)
{
      if(head == null)
          return null;
      ListNode odd = head;
      ListNode even = head.next;
      ListNode evenHead = even;
      while(even != null && even.next != null)
      {
          odd.next = odd.next.next;
          even.next = even.next.next;
          odd = odd.next;
          even = even.next;
      }
      odd.next = evenHead;
      return head;
}

奇数位链表odd，偶数位链表为even。偶数位的起始是head.next。遍历链表，node.next = node.next.next，就是将当前n位的next指向了n+2位，n为奇数则剔除了偶数位，n为偶数则剔除了奇数位；然后node = node.next就是重新指向开始节点，继续“剔除”。

876. 链表的中间结点

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。    

提示：

给定链表的结点数介于 1 和 100 之间。           

public ListNode MiddleNode(ListNode head)
{
      var slower = head;
      var faster = head;

      while(faster != null && faster.next != null)
      {
           faster = faster.next.next;
           slower = slower.next;
      }

      return slower;
}

两个指针指向head节点，一个一次走一个节点，一个一次走两个节点，当快的节点达到终点的时候，那么慢的节点正好走到中间。