链表训练3：如何优雅着反转单链表
【题目描述】
反转单链表。例如链表为：
1->2->3->4
反转后为
4->3->2->1
【要求】
如果链表的长度为 N, 时间复杂度达到 O(N), 额外空间复杂度达到 O(1)
【解答】
方法1
这道题还是挺简单的，当我们在反转一个节点的时候，把一个节点的后驱改为指向它前驱就可以了。这里需要注意的点就是，当你把当前节点的后驱指向前驱的时候，这个时候链表会被截断，也就是说后面的节点和当前节点分开了，所以我们需要一个变量来保存当前节点的后驱，以访丢失。
具体代码如下：
代码如下
//节点
class Node{
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
} //反转单链表
public static Node reverseList(Node head) {
Node next = null;//指向当前节点的后驱
Node pre = null;//指向当前节点的前驱
while (head != null) {
next = head.next;
//当前节点的后驱指向前驱
head.next = pre;
pre = head;
//处理下一个节点
head = next;
}
return pre;方法二
这道题也可以用递归来做，假设 方法 reverse() 的功能是将单链表进行逆转。采用递归的方法时，我们可以不断着对子链表进行递归。例如对于如下的链表：
我们对子链表 2->3->4 进行递归，即
Node newList = reverse(head.next)。递归之后的结果如下：
逆转之后子链表 2->3->变为了 4->3->2。
注意，我刚才假设 reverse() 的功能就是对链表进行逆转。不过此时节点 1 仍然是指向节点 2 的。这个时候，我们再把节点1 和 2逆转一下，然后 1 的下一个节点指向 null 就可以了。如图：
递归的结束条件就是：当子链表只有一个节点，或者为 null 时，递归结束。代码如下：
//用递归的方法反转链表
public static Node reverseList2(Node head){
if (head == null || head.next == null) {
return head;
}
//递归反转子lian链表
Node newList = reverseList2(head.next);
//第三张图
head.next.next = head;
head.next = null;
return newList;
}问题拓展
题目：反转部分链表节点
【题目描述】
题目：给定一个单向链表的头结点head,以及两个整数from和to ,在单项链表上把第from个节点和第to个节点这一部分进行反转
列如：
1->2->3->4->5->null,from=2,to=4
结果：1->4->3->2->5->null
列如：
1->2->3->null from=1,to=3
结果为3->2->1->null
【要求】
1、如果链表长度为N，时间复杂度要求为O（N),额外空间复杂度要求为O（1）
2、如果不满足1<=from<=to<=N,则不调整
【解答】
可以自己动手做一下或者想一下，我这里直接给出答案了
public static Node reversePart(Node head, int from, int to) {
int len = 0;//记录链表的长度
Node node1 = head;
Node fPre = null;//指向第 from-1个节点
Node tPos = null;//指向第 to + 1个节点
while (node1 != null) {
len++;
if(len == from - 1)
fPre = node1;
if(len == to + 1)
tPos = node1;
node1 = node1.next;
}
//判断给定的值是否合理
if(from > to || from < 1 || to > len)
return head;
//把from-to这部分链表进行反转
//node1指向部分链表的第一个节点
node1 = fPre == null ? head : fPre.next;
Node cur = node1.next;//cur指向当前要处理的节点
node1.next = tPos;//先把第一个节点给反转处理了
Node next = null;
while (cur != tPos) {
next = cur.next;//保存当前节点的下一个节点
cur.next = node1;
node1 = cur;
cur = next;
}
if (fPre != null) {
fPre.next = node1;
return head;
}
return node1;
}
另外，链表反转这道题一定要掌握递归版本的，因为递归版本是最不容易出错的，这道题的考察频率也是挺高的
如果喜欢本网站{https://www.iamshuaidi.com), 那么可以把该网站分享给其他人，帅地正在疯狂更新中….