单链表之：反转算法

单链表之：链表反转算法

上一篇博客讲述了一些链表的知识以及判断是否为回文串的算法，详见如何判断一个单链表是否为回文串？

一、递归方法

思路

从头节点开始，递归调用头节点的next，实际上就是从尾节点一次反转各个节点的指针指向。

来源：见参考

实现代码

/**
     * 第一种，递归 在反转当前节点之前先反转后续节点
     * @param head
     * @return
     */
    static ListNode reverse0(ListNode head) {
        if (head ==null || head.next ==null) {
            return head;
        }

        // 递归 从最后一个节点开始反转
        ListNode reHead = reverse0(head.next);
        head.next.next = head;// 自己的下一个的下一个指向自己就是反转过来了
        head.next = null;// 清空自己的next指针 相当于断开链表
        return reHead;
    }

二、非递归方法

思路

从前到后，每两个节点依次进行反转。

来源见参考

实现代码

/**
 * 不使用递归的方法，从前向后进行两两进行交换
 * @param head
 * @return
 */
static ListNode reverse1(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode prev = head;// 代表前一个节点
    ListNode cur = head.next;// 代表当前节点
    ListNode temp = null;// 代表下一个节点

    while (cur != null) {
        temp = cur.next;// 暂存下一个节点，后面赋值回来
        cur.next = prev;// 最关键的一句，当前节点next指向前一个节点，即反转了方向

        // 移动指针 整体向后移，当前节点变成前节点，下一节点变成当前节点
        prev = cur;
        cur = temp;
    }

    head.next = null;
    return prev;
}

ListNode

public class ListNode {
    public char val;
    public ListNode next;

    public ListNode(char val) {
        this.val = val;
    }

    // builder mode
    public ListNode next(ListNode next) {
        this.next = next;
        return next;
    }

    @Override
    public String toString() {
        return "{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
}

测试方法

    public static void main(String[] args) {
        ListNode head = new ListNode('a');
        head.next(new ListNode('b')).next(new ListNode('d'));
//        System.out.println(reverse0(head));
        System.out.println(reverse1(head));
    }

参考：https://blog.csdn.net/guyuealian/article/details/51119499#commentsedit