单链表反转

in 算法 with 0 comment

输入一个链表的头节点,反转该链表并输出反转后链表的头节点。

示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

看起来很简单,只需要将单链表所有结点的 next 指向,指向它的前驱节点即可。

利用栈实现反转

在原本链表的数据结构之外,引入一个栈(数组也可),将单链表循环遍历,将所有结点入栈,最后再从栈中循环出栈,记住出栈的顺序,得到的就是反转后的单链表。

实现如下:

    public Node reversalWithStack(Node head) {
        if (head == null || head.getNext() == null) {
            return head;
        }
        Stack stack = new Stack();
        while (head != null) {//循环遍历入栈
            stack.push(head);
            head = head.getNext();
        }
        Node newHead = (Node) stack.pop(); //头结点不动
        Node cur = newHead;
        while (!stack.isEmpty()) {
            Node popNode = (Node) stack.pop();//依次出栈
            cur.setNext(popNode);//cur依次移动,建立链接关系
            cur = popNode;
        }
        cur.setNext(null);//cur指针结束时一定要指向null,不然最后两个节点会相互引用的
        return newHead;
    }

但是这样实现,有一个问题,它会额外消耗一个栈的内存空间,此时空间复杂度就变成了 O(n)。

空间复杂度为 O(1) 反转

在排序算法中,有一个概念叫原地排序,指的是不需要引入额外的存储空间,在原数据结构的基础上进行排序。这种排序算法的空间复杂度是 O(1)。例如我们常见的冒泡排序、插入排序都是原地排序算法。

这里,我们也可以在原单链表的数据结构上,进行单链表反转。

递归方式

先假设后面链表都已经反转了,并把后面链表看成一个反转节点,那么只需要将当前节点和递归节点两个节点进行反转即可。

//递归方式
	public ListNode reverse(ListNode head) {
		if(head==null || head.next==null) {//递归终止条件是当前为空,或者下一个节点为空
			return head;
		}
		ListNode last = reverse(head.next);
		head.next.next = head;
		head.next = null;//防止链表循环,需要将head.next设置为空
		return last;//每层递归函数都返回last,也就是最后一个节点
	}

看起来有点不好理解,我们来步步拆解:
假设我们要反转这个链表

那么输入 reverse(head) 后,会在这里进行递归:

ListNode cur = reverse(head.next);

不要跳进递归(你的脑袋能压几个栈呀?),而是要根据刚才的函数定义,来弄清楚这段代码会产生什么结果:

这个 reverse(head.next) 执行完成后,整个链表就成了这样:

并且根据函数定义,reverse 函数会返回反转之后的头结点,我们用变量 last 接收了。

现在再来看下面的代码:

head.next.next = head;


接下来:

head.next = null;
return last;

这样整个链表就反转过来了!递归代码就是这么简洁优雅。

这里有两个地方需要注意:

  1. 递归函数都要有递归出口,也就是这句:
		if(head==null || head.next==null) {//递归终止条件是当前为空,或者下一个节点为空
			return head;
		}

意思是如果链表只有一个节点的时候反转也是它自己,直接返回即可。

  1. 当链表递归反转之后,新的头结点是 last,而之前的 head 变成了最后一个节点,别忘了链表的末尾要指向 null
		head.next = null;//防止链表循环,需要将head.next设置为空

非递归方式

双指针迭代
我们可以申请两个指针,第一个指针叫 pre,最初是指向 null 的。
第二个指针 cur 指向 head,然后不断遍历 cur。
每次迭代到 cur,都将 cur 的 next 指向 pre,然后 pre 和 cur 前进一位。
都迭代完了(cur 变成 null 了),pre 就是最后一个节点了。

动画演示如下:

动画演示中其实省略了一个tmp变量,这个tmp变量保存cur的下一个节点。

当我们要对一个结点进行指针翻转的时候,我们需要知道三个结点

  1. 待翻转的结点 cur
  2. 待反转结点的前驱结点 prev
  3. 待反转结点的下一个节点 tmp
 //非递归方式
	public ListNode reverseList(ListNode head) {
		ListNode pre = null;//申请节点,pre和 cur,pre指向null
		ListNode cur = head;
		ListNode tmp = null;
		while(cur!=null) {
			tmp = cur.next;//记录当前节点的下一个节点
			cur.next = pre;//然后将当前节点指向pre
			pre = cur;//pre和cur节点都前进一位
			cur = tmp;
		}
		return pre;
	}

数组存储

上面几种写法,都是基于单链表的数据是用链地址存储的,如果以数组形式存储数据,则可以用反转字符串的方法来实现反转!

    public void reverseWithArray(char[] originArray) {
        int from = 0;
        int to = originArray.length - 1;
        while (from < to) {//依次反转
            char tmp = originArray[from];
            originArray[from++] = originArray[to];
            originArray[to--] = tmp;
        }
    }