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)
    {
        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;
    }