链表的反转

反转链表是一道很基本的面试题，通过更改节点之间的链接来反转链表。

1.单链表的反转

题目

反转一个单链表

示例

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

用一幅图来解释：这个是初始化定义（利用迭代的方法做）

3ZF@R887ZQ$U8}13~)`7E9A.png cb1.gif

代码如下：

package com.zhoujian.solutions.leetcode;
/**
 * @author zhoujian123@hotmail.com 2018/9/14 13:15
 */
public class ReverseLinkedList {
    static Node head;
    static class Node {
        int data;
        Node next;

        Node(int d) {
            data = d;
            next = null;
        }
    }
    public static void main(String[] args) {
        Node head = new Node(85);
        head.next = new Node(15);
        head.next.next = new Node(4);
        head.next.next.next = new Node(20);
        Node node = reverse(head);
        while (node !=null){
            System.out.println(node.data+" ");
            node =node.next;
        }
    }

     static Node reverse(Node node){
        //初始化三个指针prev为NULL，curr为head，next为NULL
        Node prev = null;
        Node current = node;
        Node next =null;
        while (current !=null){
            //在更改下一个当前之前，存储下一个节点
            next = current.next;
            //将当前的next域指向前一个节点，这是实际要发生逆序的地方
            current.next = prev;
            //将prev和current向后移动
            prev = current;
            current = next;
        }
        node = prev;
        return node;
    }
}

image.png

时间复杂度为O(n)，空间复杂度为O(1)。

2.双链表的链表

image.png

代码和解释如下：

package com.zhoujian.solutions.leetcode;

/**
 * @author zhoujian123@hotmail.com 2018/9/14 13:51
 */
public class ReverseDoubleNode {

    static DoubleNode head;
    static class DoubleNode {
        int data;
        DoubleNode next, prev;
        DoubleNode(int d) {
            data = d;
            next = prev = null;
        }
    }
    public static DoubleNode reverseList(DoubleNode head){
       DoubleNode current = head;
       DoubleNode pre =null;
       DoubleNode next = null;
       while (current != null){
           //存储下一个节点
           next = current.next;
           //发生反转
           current.next = pre;
           current.prev = next;
           //指针往下一个节点移动
           pre = current;
           current =next;
       }
        return pre;
    }

    public static void main(String[] args) {
        DoubleNode head = new DoubleNode(85);
        head.next = new DoubleNode(15);
        head.next.prev = head;
        head.next.next = new DoubleNode(20);
        head.next.next.prev = head.next;
        head.next.next.next = new DoubleNode(4);
        head.next.next.next.prev = head.next.next;
        printDoubleLinkedList(reverseList(head));
    }

    public static void printDoubleLinkedList(DoubleNode head) {
        System.out.print("Double Linked List: ");
        while (head != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }
    }
}

image.png

时间复杂度为O(n)，空间复杂度为O(1)。