三种方法搞定单链表逆序

单链表是比较基础的数据结构,也是应用非常广泛的数据结构之一,涉及的算法题也很多,本篇文章主要介绍三种方法解决单链表逆序(反转单链表)的相关问题,其中包括非递归和递归的实现策略。


了解单链表逆序

单链表逆序是一道基础的数据结构算法题,在数据结构的课程中,必定会涉及到。

单链表逆序这里提供三种思路,它们分别从递归和非递归的角度解决这个问题,无论是哪一种方法,万变不离其宗,单链表逆序的本质都是将每一个节点原来指向的下一个节点的next指针指向它前面的那个节点。如果采用非递归的方法,需要同时知道单链表的三个节点,这种方法有明显的规律可循。如果采用递归的方法,虽然只需要知道头节点,但是并没有非递归容易理解。

首先给出单链表节点的定义,本篇文章都是基于带头节点的单链表:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public class SinglyNode<T> {
protected T data;
protected SinglyNode<T> next;
public SinglyNode() {
this(null,null);
}
public SinglyNode(T data) {
this(data,null);
}
public SinglyNode(T data,SinglyNode<T> next) {
this.data=data;
this.next=next;
}
@Override
public String toString() {
return data.toString();
}
}

非递归解决单链表逆序

非递归的方法根据操作方式的不同,分为两种类型,暂且就叫做最终头节点法和实时头节点法吧。

对于这两种方法,都需要同时知道三个节点,假设为p1,p2,p3,并且请记住,当p2==null时结束算法
假设单链表有四个节点[1,2,3,4]

最终头节点法

最终头节点法的含义是到最后才更改单链表的头节点的next指针。
下面的图片展示了这种方法的详细过程:

最终头节点法的过程

从上述过程可以看到:核心的操作是p2.next=p1(将后一个节点的next指向之前的节点),然后向后移动节点,直到p2==null

但是不知道你有没有发现,这个过程存在一个小问题:在1和2节点之间出现了环(并且只会在前两个节点间出现环),这是遍历链表必须要避免的大问题,这会导致死循环。所以在具体的代码中,应该要避免这一问题。
下面是具体的代码实现,以及如何避免环:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public SinglyList reverse(SinglyList<T> list) {
if(list.head.next==null||list.head.next.next==null) {
return list;
}
SinglyNode<T> p1=list.head.next;
SinglyNode<T> p2=list.head.next.next;
SinglyNode<T> p3=null;
while(p2!=null) { //结束条件
p3=p2.next; //仔细思考,注意循环中语句的顺序
p2.next=p1;
if(p1==list.head.next) { //避免环
p1.next=null;
}
p1=p2;
p2=p3;
}
list.head.next=p1; //最终改变头节点
return list;
}

实时头节点法

实时头节点法的含义是每一步都需要更改头节点的next指针。
这种方法和上面的方法操作方法不太一样,具体的过程如下图:
实时头节点法的过程

实时头节点法的思想将第一个节点(1)之后的每一个节点都插入头节点和第一个节点之间,并且整个过程不会改变头节点和p1
结束的条件也是p2==null

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public SinglyList reverse(SinglyList<T> list) {
if(list.head.next==null||list.head.next.next==null) {
return list;
}
SinglyNode<T> p1=list.head.next;
SinglyNode<T> p2=list.head.next.next;
SinglyNode<T> p3=null;
while(p2!=null) {
p3=p2.next;
p1.next=p3;
p2.next=list.head.next;
list.head.next=p2;
p2=p3;
}
return list;
}

递归解决单链表逆序

如果逆序两个节点,这是非常简单的,假设有两个节点p1,p2,逆序的操作是p2.next=p1,p1.next=null。

如果是三个节点呢?假设三个节点为p1,p2,p3。
递归的思想是将大问题分解为小问题,所以我们可以将p2,p3看成一个整体p23,
如果p23内部已经是逆序的,我们的操作是:p2.next=p1,p1.next=null;
p23内部的操作是:p3.next=p2,p2.next=null。
所以对于一个单链表来说,可以分为第一个节点和剩余节点两部分,剩余节点再分为第一个和剩余节点…以此类推
每一层都执行p2.next=p1,p1.next=null,直到最后分割到只剩最后一个节点,并返回这个节点(它将是新的链表头),这是递归结束的条件(这一点非常重要)。
详细的过程图如下:
递归过程
图中黑色序号标明了递归的流程

代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public SinglyList reverse(SinglyList<T> list) {
list.head.next=reverseWithRecursion(list.head.next);
return list;
}

private SinglyNode reverseWithRecursion(SinglyNode head) {
if(head==null||head.next==null) { //递归结束条件
return head;
}
SinglyNode newHead=reverseWithRecursion(head.next);
SinglyNode temp=head.next;
temp.next=head;
head.next=null;
return newHead;
}

smartpig wechat
扫一扫关注微信公众号
0%