单链表的反转

74 次访问 2019-09-22

郑瑶

单链表的反转

一般单链表反转有三种方法

链表转为数组反转后再转为链表
递归反转
三指针反转

链表和节点代码

  public class SinglyLinkedList {
    /**
     * head指针
     */
    private Node head = null;

    public SinglyLinkedList(){
        head = new Node();
    }
}

Node代码

    public Node next;
    public int value;
     Node(){}
     Node(int value){
        this.value = value;
    }

数组转换法

这种方法就比较简单粗暴了,直接声明一个链表相同大小的数组,遍历链表,从数组的最后一位开始赋值,然后再遍历数组,将链表重新赋值,耗时O(n),空间大小O(n),所以这种方式一般不会使用

/**
     * @Description: 使用数组方法进行单链表的反转,浪费空间
     * @Params: []
     * @return: void
     * @Author: zhengyao
     * @Date: 2019/8/9
     */
    private  void reverseListByArray(){
        if(reverseListLengthValidate()){
            int[] array = new int[getLength()];
            Node current = head.next;
            int index = getLength() - 1;
	    //遍历链表,赋值给数组	
            while (current != null){
                array[index] = current.value;
                current = current.next;
                index--;
            }
	    //遍历数组,赋值给链表
            Node reverseHead = head;
            for (int value : array) {
                reverseHead.next = new Node(value);
                reverseHead = reverseHead.next;
            }
        }
    }

递归法

其实就是递归到链表的最后一个节点,然后将每一个节点的next.next变成自己,就达到了反转链表的功能

    /**
     * @Description: 反转链表,使用递归法进行反转,例如3->4->5->6,
     * 递归之后就变成,当head等于5的时候,5->6->5->null,return 6,回来,就直接反转了整个节点
     * @Params: []
     * @return: void
     * @Author: zhengyao
     * @Date: 2019/8/9
     */
    private void reverseList(){
        Node curr = reverseListByre(head.next);
        head.next = curr;
    }
    private Node reverseListByre(Node head){
        if(head == null || head.next == null){
            return head;
        }
        Node curr = reverseListByre(head.next);
        //将本节点的next.next变成自己,就变成了反转了,我的下一步变成了我,然后将我的next置为null,否则会死循环
        head.next.next = head;
        head.next = null;
        return curr;
    }

三指针反转法

/**
     * @Description: 使用三个指针来反转链表
     * @Params: []
     * @return: void
     * @Author: zhengyao
     * @Date: 2019/8/9
     */
    private void reverseListByPointer(){
        if(reverseListLengthValidate()){
            //head 不拿出来进行计算
            Node curr = head.next;
            Node prev = null;
            while (curr != null){
                // 先记录下当前指针的下一个,留着后面给curr指针移动使用
                Node temp = curr.next;
                // 最早的prev是null,后面每一次prev = 当前指针,留待下一个循环,指向前一个prev
                curr.next = prev;
                // 这里就是将prev = 当前指针,每次都比当前指针慢一步,相当于把原有的前置指针变为现有的后置指针
                prev = curr;
                // 当前指针移动到下一步
                curr = temp;
            }
            head.next = prev;
        }

    }