一.简介
挑选了几道常考的反转链表题，链表是通过指针将一组零散的内存串联在一起，反转充分了利用指针来操作。（不限语言，本文是Java示例）
二.示例
2.1 反转链表
反转一个单链表，例如把1->2->3->null 反转 3->2->1->null 形式，指针反转，不仅仅是值的变化。
迭代
迭代的形式，按照一般思路先有一个指针指向前驱结点，每次都在移位前驱结点，这样把指针反转过来。
public void reverseList(ListNode head){
ListNode reList = null;
//前驱
ListNode prev = null;
//当前
ListNode curr = head;
while (curr != null){
//指向下一个结点
ListNode next = curr.getNext();
if(next == null){
reList = curr;
}
//当前结点指向前驱结点，例如 1-> null
curr.setNext(prev);
//前驱结点被赋值 1-> null
prev = curr;
// 2-> 3 如此进行迭代
curr = next;
}
return reList;
}
递归
public ListNode reverseList(ListNode head) {
return reverseList2(null,head);
}
//跟迭代类似，运用前驱结点，每次递归，把提前存储在内存中next ,这样累加前驱结点地址
ListNode reverseList2(ListNode prev,ListNode curr){
if(curr == null) return prev;
ListNode next = curr.next;
curr.next = prev;
return reverseList2(curr,next);
}
2.2 两两交换链表中的节点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表，你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
迭代
因为从第一个结点开始反转，这样引入哨兵，不参与计算，站位好处理第一个结点，解决邻居依赖问题。
public ListNode swapPairs(ListNode head) {
ListNode prev = new ListNode(0);
prev.next = head;
//前驱结点
ListNode p1 = prev;
ListNode p2 = null;
while(p1.next != null && p1.next.next != null){
p2 = p1.next;//p2 等于 下一个结点 1->2->3->4
p1.next = p2.next;//这两步骤把第二结点，赋值到 0 -> 2
//1->3->4 跳过2结点，因为要反转，把2结点放到第一位
p2.next = p2.next.next;
//0->2->1->3->4 第一组反转完毕
p1.next.next = p2;
//赋值p1 因为要进入下一组
p1 = p2;
}
return prev.next;
}
递归
public ListNode swapPairs(ListNode h) {
if (h == null || h.next == null) {
return h;
}
ListNode newHead = h.next;
//这个递归是要把 3 -> 4，反转 4-> 3 ,然后返回上层再处理第一组1->2的反转
h.next = swapPairs(newHead.next);
newHead.next = h;
return newHead;
}
2.3 k个一组反转链表
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例
给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
结点列表每k个就反转，相当于把2.2 两辆反转变形了。
因为从第一个结点开始反转，这样引入哨兵，不参与计算，站位好处理第一个结点，解决邻居依赖问题，这个难度比较大，得需要借助图形更加深理解。
public void reverseKGroup(int k){
ListNode hair = new ListNode(0);
//头结点
ListNode head2 = head;
hair.setNext(head2);
ListNode pre = hair;
while (head2 != null) {
ListNode tail = pre;
// 查看剩余部分长度是否大于等于 k
for (int i = 0; i < k; ++i) {
tail = tail.getNext();
if (tail == null) {
break;
}
}
ListNode nex = tail.getNext();
//反转，k个结点
ListNode[] reverse = myReverse(head2, tail);
//已经反转完毕的，一组结点
head2 = reverse[0];
//一组结点的后继结点
tail = reverse[1];
// 把子链表重新接回原链表
pre.setNext(head2);
tail.setNext(nex);
//这个是处理下一组的结点
pre = tail;
head2 = tail.getNext();
}
return hair.getNext();
}
/**
* 反转
*/
private ListNode[] myReverse(ListNode curr,ListNode tail){
ListNode prev = tail.next;
ListNode p = curr;
//反转完毕，地址相等的判定
while (prev != tail) {
ListNode nex = p.next;
p.next = prev;
prev = p;
p = nex;
}
return new ListNode[]{tail, curr};
}
参考
https://leetcode-cn.com/problems/reverse-linked-list/
https://leetcode-cn.com/problems/swap-nodes-in-pairs/
https://leetcode-cn.com/problems/reverse-nodes-in-k-group/?utm_source=LCUS&utm_medium=ip_redirect&utm_campaign=transfer2china
