- Leetcode 19 Remove Nth Node From End of List
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：给定的 n 保证是有效的。
进阶：你能尝试使用一趟扫描实现吗？
解题说明：
注意，这个题有可能删除头结点，所以首先创建一个虚拟节点，虚拟节点的好处就是头结点可能被删掉，而虚拟节点不会被删掉。
方法一：先得到整个列表的长度，注意考虑一些极端情况的出现，比如删除元素位于链表的开头或者结尾，亦或是不存在的情况。然后开始第二轮遍历，遍历到length-n的位置的时候调过下一个目标，去到下下一个目标。
只扫描一次的情况
方法二：双指针算法：
- 创建虚拟指针，
- 采用两个指针，一个先走n步，
- 然后第二个和第一个一起走，当第一个走完的时候，第二个刚好走到倒数第n的位置，
- 然后慢指针跳过下一个位置。
# method 1
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
# get the length of list
length = 0
tmp = head
while tmp:
tmp = tmp.next
length += 1
# exceptions
if length == n:
return head.next
if length == 0:
return
if length - n < 0:
return head
i = 1
cur_node = head
while cur_node:
if i == length - n:
cur_node.next = cur_node.next.next
else:
cur_node = cur_node.next
i += 1
return head
# method 2
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
# 采用悬挂指针的方式
prehead = ListNode(0)
prehead.next = head
fast_cur = slow_cur = prehead
i = 0
#注意在这里控制极端情况的发生
while i <=n and fast_cur:
fast_cur = fast_cur.next
i += 1
while fast_cur:
fast_cur = fast_cur.next
slow_cur = slow_cur.next
slow_cur.next = slow_cur.next.next
return prehead.next
- Leetcode 237 删除链表中的结点
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。
现有一个链表 -- head = [4,5,1,9]，它可以表示为:
图片.png
输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
解题思路：
由于删除的点不是尾结点，所以可以伪装成下一个点，然后删除下一个点
# 解法一
class Solution(object):
def deleteNode(self, node):
"""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
"""
node.val = node.next.val
node.next = node.next.next
- Leetcode 83. 删除排序链表中的重复数字
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:
输入: 1->1->2
输出: 1->2
解题思路：注意是排序链表，分为两种情况：如果下一个点和当前点相似，则删掉下一个点；否则指针移动到下一个点。因此只需要扫描一遍。
class Solution(object):
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
cur = head
while cur:
if cur.next and cur.val == cur.next.val:
cur.next = cur.next.next
else:
cur = cur.next
return head
Leetcode 61. 旋转链表
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
示例 2:
输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL
解题说明：
- 先让k对n取模；
- 可以采用双指针的做法，得到最后一个点和倒数第n+1个点的位置（注意不需要创建虚拟头结点了）；
- 改变头结点和尾结点为位置。
class Solution(object):
def rotateRight(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
# exception
if head == None:
return
# get the length of list
n = 0
cur = head
while cur:
cur = cur.next
n += 1
k = k%n
# fast and slow cur
fast = slow = head
i = 1
while i<=k:
fast = fast.next
i += 1
while fast.next:
fast = fast.next
slow = slow.next
# change the head and tail
fast.next = head
head = slow.next
slow.next = None
return head
- Leeetcode 24. 两两交换链表中的结点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
解题思路：
p为虚拟节点， 第一步p指向b，第二步a指向3，第三步b指向a，第四步p移动到a。这样就完成了一个循环。
class Solution(object):
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head == None:
return
p = ListNode(0)
p.next = head
cur = p
while p.next and p.next.next:
a = p.next
b = a.next
p.next = b
a.next = b.next
b.next = a
p = a
return cur.next
- Leetcode 206. 反转链表
反转一个单链表。示例:
输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
解题思路：
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head == None:
return
a = head
b = a.next
while b:
c = b.next
b.next = a
a = b
b = c
head.next = None
return a
- Leetcode 92. 反转链表 II
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
解题思路：
class Solution(object):
def reverseBetween(self, head, m, n):
"""
:type head: ListNode
:type m: int
:type n: int
:rtype: ListNode
"""
if head == None or head.next == None or m >= n or m < 0 or n < 0:
return head
# virtual node
prehead = ListNode(0)
prehead.next = head
# get the position before m and n
t1 = prehead
t2 = prehead
i = 0
j = 0
while i < m-1:
t1 = t1.next
i += 1
while j < n:
t2 = t2.next
j += 1
# reverse
a = t1.next
b = t2.next
p = a
q = a.next
while q != b:
o = q.next
q.next = p
p = q
q = o
# connect the reversed chain
t1.next = p
a.next = b
return head
Leetcode 92. 相交链表
编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。在节点 c1 开始相交。
解题思路：
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
p = headA
q = headB
while(p!=q):
if p:
p = p.next
else:
p = headB
if q:
q = q.next
else:
q = headA
return p
Leetcode 142. 环形链表
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。
解题思路：
(链表，快慢指针扫描) O(n)
本题的做法比较巧妙。用两个指针 first,second分别从起点开始走，first 每次走一步，second 每次走两步。如果过程中 second 走到null，则说明不存在环。否则当 first 和 second 相遇后，让 first 返回起点，second待在原地不动，然后两个指针每次分别走一步，当相遇时，相遇点就是环的入口。
证明：如上图所示，a
是起点，b 是环的入口，c 是两个指针的第一次相遇点，ab 之间的距离是 x，bc 之间的距离是 y。则当 first 走到 b 时，由于 second 比 first 多走一倍的路，所以 second 已经从 b 开始在环上走了 x 步，可能多余1圈，距离 b 还差 y 步（这是因为第一次相遇点在 b 之后 y 步，我们让 first 退回 b 点，则 second 会退 2y 步，也就是距离 b 点还差 y 步）；所以 second 从 b 点走 x+y 步即可回到 b 点，所以 second 从 c 点开始走，走 x 步即可恰好走到 b 点，同时让 first 从头开始走，走 x 步也恰好可以走到 b 点。所以第二次相遇点就是 b 点。
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head == None or head.next == None:
return None
fast = head
slow = head
while fast and slow:
fast = fast.next
slow = slow.next
if fast:
fast = fast.next
else:
return None
if fast == slow:
slow = head
while fast != slow:
fast = fast.next
slow = slow.next
return slow
return None
