链表作为一种常用的数据结构，面试当然也是家常便饭。此处就来谈谈关于链表面试中的的几种常见反转。
1.逆序所有节点
输入：list = 1->2->3->4->5->null
输出：list = 5->4->3->2->1->null
思路：定义previous、current、next（即前驱、当前、后继）指针。从头结点开始往后一个个逆序，即不断让current.next = previous即可。
JAVA参考代码
public class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
public ListNode reverse(ListNode current) {
ListNode previous = null; //前驱结点
while (current != null) {
//next记录下一个节点，current是当前节点
ListNode next = current.next;
current.next = previous;
previous = current;
current = next;
}
return previous;
}
2.逆序第m到n个节点(1 ≤ m ≤ n ≤ size)
输入: list = 1->2->3->4->5->6->null, m = 2 and n = 5,
输出: list = 1->5->4->3->2->6->null
思路：找出原链表中第m到n个元素，进行逆序后。再接回原来的链表中。
- a.找出原链表中m的前一个结点mPrevNode；
- b.取出原链表第m到n个元素，进行逆序；
- c.记录原链表中n的下一个结点nNextNode；
- d.原链表结点mPrevNode指向逆序后的头结点；
- e.逆序后的尾结点指向原链表结点nNextNode。
JAVA参考代码
public ListNode reverse4Range(ListNode head, int m, int n) {
if (m >= n || head == null) {
return head;
}
ListNode newList = new ListNode(0);
newList.next = head;
head = newList;
for (int i = 1; i < m; i++) {
if (head == null) {
return null;
}
head = head.next;
}
ListNode mPreNode = head;
ListNode mNode = head.next;
ListNode nNode = mNode, nNextNode = mNode.next;
for (int i = m; i < n; i++) {
if (nNextNode == null) {
return null;
}
ListNode temp = nNextNode.next;
nNextNode.next = nNode;
nNode = nNextNode;
nNextNode = temp;
}
mNode.next = nNextNode;
mPreNode.next = nNode;
return newList.next;
}
3.按K个值分组逆序
即从头结点开始每k个逆序，若小于k个则不做处理。
输入：list = 1->2->3->4->5->null, k=3
输出：list = 3->2->1->4->5->null
思路：顺序按k个一组执行逆序
- a.记录前一个k组逆序的尾结点 prevTail；
- b.记录下一组的头结点 nextGroupHead；
- c.找到k个结点则进行该组逆序， 若不足k个则直接指向后结点；
- d.前一个尾结点 prevTail 指向逆序后的头结点 reverseHead。
JAVA参考代码
public ListNode reverse4KGroup(ListNode head, int k) {
ListNode newList = new ListNode(0);
ListNode prevTail = newList;
ListNode nextGroupHead = head;
while (head != null) {
for (int i = 0; i < k-1 && head != null; i++) {
head = head.next;
}
if (head != null) {
ListNode nextHead = head.next;
head.next = null;
ListNode reverseHead = reverse(nextGroupHead); // 题1中的reverse()
prevTail.next = reverseHead;
prevTail = nextGroupHead;
nextGroupHead = nextHead;
head = nextGroupHead;
} else {
prevTail.next = nextGroupHead;
}
}
return newList.next;
}
public ListNode reverse(ListNode current) {
ListNode previous = null; //前驱结点
while (current != null) {
//next记录下一个节点，current是当前节点
ListNode next = current.next;
current.next = previous;
previous = current;
current = next;
}
return previous;
}
