算法学习：(单)链表问题

2018年6月17日

一 链表倒置

Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
A linked list can be reversed either iteratively or recursively. Could you implement both?

• 迭代方法
如图： 两个指针 head p 分别指向 表头，欲倒置的元素. 为了使下一个欲倒置的元素不会  掉， 还需要一个指针 tmp 来保护它

3. head = p, p = tmp, tmp 保护下一个欲倒置的元素

代码：

• 递归方法
思想和上面一样，只不过代码的写法不同：

递归的方法代码简洁高效，在很多链表题目中都会用到它，所以特别重要。例如下一题

LeetCode 92. Reverse Linked List II

Reverse a linked list from position m to n. Do it in one-pass.
Note: 1 ≤ m ≤ n ≤ length of list.
Example:
Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

二 快慢指针

LeetCode 876. Middle of the Linked List

If there are two middle nodes, return the second middle node.
Example 1:
Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3. (The judge’s serialization of this node is [3,4,5]).
Note that we returned a ListNode object ans, such that:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.
Example 2:
Input: [1,2,3,4,5,6]
Output: Node 4 from this list (Serialization: [4,5,6])
Since the list has two middle nodes with values 3 and 4, we return the second one.

• 234. Palindrome Linked List 判断回文链表： 找到链表的中点，将其一半倒置，再比较元素是否相同即可。也许使用栈等容器来解会现快一些，但会增加空间复杂度。
• 待添加

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.

1. 环中有多少个节点
2. 环首在什么位置

题目三： 142. Linked List Cycle II

LeetCode 142. Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
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.

1. 本文目前尚无任何评论.