题目：
Sort a linked list in O(n log n) time using constant space complexity.
分析：
排序一个链表。要求O(nlogn)时间，O(1)空间。
说到O(nlogn)时间，首先想到的是合并排序。虽然合并排序对于数组是O(n)空间，但是对于链表却可以做到O(1)空间。
Tag Archives: 链表
LeetCode #147 Insertion Sort List (链表插入排序)
题目：
Sort a linked list using insertion sort.
分析：
使用插入排序法对一个链表进行排序。
没有什么特别深奥之处。注意处理好边界情况即可。
LeetCode #109 Convert Sorted List to Binary Search Tree (有序链表转换为平衡二叉搜索树)
题目：
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
分析：
给定一个有序链表，将其转换为一个高度平衡的二叉搜索树。
首先遍历链表获得链表长度。之后通过递归生成二叉搜索树。其生成过程和树的中序遍历类型：先是左子树，然后是根节点，最后是右子树。每添加一个树节点，就把链表节点的值赋给树节点，然后指针指向下一个链表节点。
Continue reading LeetCode #109 Convert Sorted List to Binary Search Tree (有序链表转换为平衡二叉搜索树)
LeetCode #237 Delete Node in a Linked List
题目：
Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
Supposed the linked list is
1 -> 2 -> 3 -> 4and you are given the third node with value3, the linked list should become1 -> 2 -> 4after calling your function.
分析：
删除链表中的指定节点。
这道题目很有意思。没有给出链表的头结点，因此也就无法知道要删除节点的前一个节点。这怎么能行呢？乍一看是个不可能完成的任务。其实不然。我们在做链表操作的时候往往有一种思维定式，光想着修改next，却想不到还可以修改val。直接把下一个节点的值复制到当前节点，然后再按照一般方法删除下一个节点即可。
另外注意一下，使用C或者C++等语言时，要防止内存泄露。
代码：
Java
|
1 2 3 4 5 6 |
public class Solution { public void deleteNode(ListNode node) { node.val = node.next.val; node.next = node.next.next; } } |
LeetCode #141 Linked List Cycle
题目：
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
分析：
检查链表是否有圈。
题目要求不能使用多余的空间。于是这里使用Floyd判圈算法，又称龟兔赛跑算法。算法逻辑如下：
- 指针hare初始化指向链表头结点，每次向后移动2个节点。
- 指针tortoise初始化指向链表头结点，每次向后移动1个节点。
- 如果hare最终指向尾节点或尾节点前一个节点（总结点数可能是奇数也可能是偶数），则该链表无圈。
- 如果hare和tortoise又指向了同一个节点，则该链表有圈。
通俗点的解释就是：龟兔赛跑，如果是一条直线，兔子永远会跑在前面；如果兔子发现又追上乌龟了，那么只能是兔子套了乌龟一圈。