例题：LeetCode 第 19 题：删除链表的倒数第 N 个结点
传送门：英文网址：19. Remove Nth Node From End of List ，中文网址：19. 删除链表的倒数第N个节点 。
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5.说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
思路：使用快慢指针。其实只要掌握了如何找到距离末尾 个元素的位置，就很容易了。还要注意的就是边界值的选取，其实往往我们认为的值与正确值无非就是
或者
，为了避免粗心出错，我们可以拿一个具体的例子。另外，涉及链表头结点的操作，一般都会引入虚拟结点，以减少讨论的可能，这是一个常见的技巧。
Python 代码：
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def findKthToTail(self, pListHead, k):
"""
:type pListHead: ListNode
:type k: int
:rtype: ListNode
"""
if pListHead is None:
return None
fast = pListHead
# 要注意的临界点1：
for _ in range(k - 1):
fast = fast.next
if fast is None:
return None
slow = pListHead
# 要注意的临界点2：
while fast.next:
slow = slow.next
fast = fast.next
return slow
练习1：LeetCode 第 61 题：旋转链表
传送门：英文网址：61. Rotate List ，中文网址：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
思路：问题本身不难，但是要处理一些细节。
1、一定要先求出链表的总长度；
2、求得总长度的时候，顺便标记好末尾结点，并且把末尾结点的 next 指针指到头结点去，形成环，否则容易出现空指针异常；
3、到底多少 pre 指针还要走多少步，举 1 到 2 个具体的例子带进去就知道了。
Python 代码：
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def rotateRight(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if head is None or k <= 0:
return head
# 先看链表有多少元素
node = head
# 先数这个链表的长度
counter = 1
while node.next:
node = node.next
counter += 1
node.next = head
k = k % counter
node = head
# counter - k - 1 可以取一些极端的例子找到规律
for _ in range(counter - k - 1):
node = node.next
new_head = node.next
node.next = None
return new_head
练习2：LeetCode 第 143 题：重排链表
传送门：143. 重排链表。
给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3.示例 2:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
Java 代码：
/**
* @author liwei
* @date 18/7/5 上午9:36
*/
public class Solution2 {
public void reorderList(ListNode head) {
if (head == null || head.next == null) {
return;
}
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode anotherHead = slow.next;
// 步骤1：从中间截断链表
slow.next = null;
// 步骤2：反转链表的后半截
ListNode reverseList = reverseList(anotherHead);
// 步骤3：合并两个链表
int k = 0;
mergeTwoList(head, reverseList, k);
}
private ListNode mergeTwoList(ListNode head1, ListNode head2, int k) {
if (head1 == null) {
return head2;
}
if (head2 == null) {
return head1;
}
// k % 2 == 0
if ((k & 1) == 0) {
head1.next = mergeTwoList(head1.next, head2, ++k);
return head1;
} else {
head2.next = mergeTwoList(head1, head2.next, ++k);
return head2;
}
}
private ListNode reverseList(ListNode head) {
ListNode preNode = null;
ListNode curNode = head;
while (curNode != null) {
ListNode nextNode = curNode.next;
curNode.next = preNode;
preNode = curNode;
curNode = nextNode;
}
return preNode;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 5};
Solution2 solution2 = new Solution2();
ListNode head = new ListNode(nums);
solution2.reorderList(head);
System.out.println(head);
}
}
练习3：LeetCode 第 234 题：回文链表
传送门：234. 回文链表。
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2 输出: false示例 2:
输入: 1->2->2->1 输出: true进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
求解关键：找到链表中间位置的结点，做一些相关的处理。特别要注意的是，不管哪种方法，都要对一些细节问题仔细考虑，可以举出具体的例子，画图帮助编码实现。
思路1：从中间位置开始反转链表，逐个比较。
Java 代码：
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
public ListNode(int[] nums) {
if (nums == null || nums.length == 0) {
throw new IllegalArgumentException("arr can not be empty");
}
this.val = nums[0];
ListNode curr = this;
for (int i = 1; i < nums.length; i++) {
curr.next = new ListNode(nums[i]);
curr = curr.next;
}
}
@Override
public String toString() {
StringBuilder s = new StringBuilder();
ListNode cur = this;
while (cur != null) {
s.append(cur.val + " -> ");
cur = cur.next;
}
s.append("NULL");
return s.toString();
}
}
/**
* https://leetcode-cn.com/problems/palindrome-linked-list/description/
*
* @author liwei
*/
public class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// slow 的下一个就是新链表，反转它
ListNode cur = slow.next;
slow.next = null;
ListNode pre = null;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
// 此时 pre 成为新链表开头
while (head != null && pre != null) {
if (head.val != pre.val) {
return false;
}
head = head.next;
pre = pre.next;
}
return true;
}
public static void main(String[] args) {
int[] nums = {1, 2, 0, 2, 1};
Solution solution = new Solution();
ListNode head = new ListNode(nums);
boolean palindrome = solution.isPalindrome(head);
System.out.println(palindrome);
}
}
思路2：在寻找链表中间结点的过程中，慢结点向前遍历的时候，把遍历到的值放入一个栈中。
Java 代码：
import java.util.Stack;
/**
* @author liwei
*/
public class Solution2 {
// 分清楚奇数和偶数结点两种情况，不反转链表，借助栈完成回文链表的判断
// slow
// 1，2，3，4，5
// slow
// 1，2，3，4
/**
* @param head
* @return
*/
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
Stack<Integer> stack = new Stack<>();
ListNode fast = head;
ListNode slow = head;
stack.add(slow.val);
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
stack.add(slow.val);
}
if (fast.next == null) {
// 链表有奇数个结点
stack.pop();
}
slow = slow.next;
while (slow != null) {
if (stack.pop() != slow.val) {
return false;
}
slow = slow.next;
}
return true;
}
public static void main(String[] args) {
Solution2 solution2 = new Solution2();
int[] nums = {1, 2, 3, 2, 1};
ListNode head = new ListNode(nums);
boolean palindrome = solution2.isPalindrome(head);
System.out.println(palindrome);
}
}
（本节完）
