《程序员代码面试指南》第二章 链表问题 反转单向链表和双向链表

题目

反转单向链表和双向链表

java代码

/**
 * @Description:反转单向链表和双向链表
 * @Author: lizhouwei
 * @CreateDate: 2018/4/6 11:07
 * @Modify by:
 * @ModifyDate:
 */
public class Chapter2_4 {
    //反转单向链表
    public Node reverse(Node head){
        if(head ==null){
            return null;
        }
         Node pre = null;
        Node next=null;
        while (head!=null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return  pre;
    }

    //反转双向链表
    public DoubleNode reverseDNode(DoubleNode head){
        if(head ==null){
            return null;
        }
        DoubleNode pre = null;
        DoubleNode next=null;
        while (head!=null){
            next = head.next;
            head.next = pre;
            head.pre = next;
            pre = head;
            head = next;
        }
        return  pre;
    }
    public void printLink(Node head) {
        System.out.println();
        while (head != null) {
            System.out.print(head.vlaue + " ");
            head = head.next;
        }
    }

    public void printDLink(DoubleNode head) {
        System.out.println();
        while (head != null) {
            System.out.print(head.vlaue + " ");
            head = head.next;
        }
    }

    //测试
    public static void main(String[] args) {
        Chapter2_4 chapter = new Chapter2_4();
        Link link1 = new Link();//单链表
        Link link2 = new Link();//双链表

        //构造链表
        for (int i = 10; i > 0; i--) {
            link1.add(i);
            link2.addDoubleNode(i);
        }
        chapter.printLink(link1.head);
        Node head = chapter.reverse(link1.head);
        chapter.printLink(head);
        chapter.printDLink(link2.dhead);
        DoubleNode dhead = chapter.reverseDNode(link2.dhead);
        chapter.printDLink(dhead);

    }
}