#### 21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Test

#### 24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head. You may not modify the values in the list’s nodes, only nodes itself may be changed.

Test

#### 61. Rotate List

Given a linked list, rotate the list to the right by k places, where k is non-negative.

#### 86. Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions.

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Runtime: 1144 ms, faster than 5.08% of Python online submissions for Linked List Cycle.

#### 143. Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You may not modify the values in the list’s nodes, only nodes itself may be changed.

• 先把 A 的下一位保存，然后指向 B，指针下移一位
• 当前指针的下一位指向上一步保存的位置
• 指针下移一位，链表二指针也下移一位

#### 160. Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

• 保存当前头结点的下个节点。
• 将当前头结点的下一个节点指向“上一个节点”，这一步是实现了反转。
• 将当前头结点设置为“上一个节点”。
• 将保存的下一个节点设置为头结点。

#### 328. Odd Even Linked List

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

• 先初始化两个小狗并保存，它们的 next 分别指向 headhead.next，然后让小狗各自站到自己的 next 上（此时两只小狗是错位的）
• 检查 even 小狗是不是 None，是的话就赋给 head 结束循环，不是的话就让 head 指针向后两步（开始检查循环）
• 循环结束之后，令 odd 小狗的 next 指向初始化时保存的 even 小狗的 next
• 返回 even 小狗的备份的 next

Return the number of connected components in G, where two values are connected if they appear consecutively in the linked list.

#### 876. Middle of the Linked List

Given a non-empty, singly linked list with head node head, return a middle node of linked list. If there are two middle nodes, return the second middle node.

Test