当前位置:   article > 正文

Java实现单链表的反转_单链表反转java实现

单链表反转java实现

方式一:直接反转

  • 对链表的某个节点Node执行指针反转时,同时需要知道当前Node的前驱Node、后继Node。
public class Node {

    public Node next; //后置节点
    public String content; //节点内容

    public Node(String content, Node next) {
        this.content = content;
        this.next = next;
    }

    @Override
    public String toString() {
        String nextNodeContent = next != null ? next.content : null;
        return "{" + content + ",next :" + nextNodeContent + "}";
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
public static void main(String[] args) {
    //初始化链表
    Node head = initList();

    //方式一:直接反转
    Node newHead = reverse(head);
    System.out.println("新的头结点:" + newHead);
}

private static List<Node> nodes = new LinkedList<>();

/**
 * 初始化链表
 *
 * @return 头结点Head
 */
private static Node initList() {
    Node eNode = new Node("E", null);
    Node dNode = new Node("D", eNode);
    Node cNode = new Node("C", dNode);
    Node bNode = new Node("B", cNode);
    Node aNode = new Node("A", bNode);
    nodes.add(aNode);
    nodes.add(bNode);
    nodes.add(cNode);
    nodes.add(dNode);
    nodes.add(eNode);
    System.out.println("初始链表:" + nodes);
    return aNode;
}

/**
 * 方式一:直接反转
 *
 * @param head 链表的头结点
 */
private static Node reverse(Node head) {

    if (head == null || head.next == null) {
        //如果当前链表为空或链表只有一个节点Node 直接返回
        return head;
    }

    Node curNode = head;
    Node nextNode;//指向下一个要执行的Node
    Node preNode = null; //指向上一个执行的Node

    while (curNode != null) {
        nextNode = curNode.next; //next指针后移
        curNode.next = preNode; //当前Node的指针反转
        preNode = curNode; // pre指针后移
        curNode = nextNode;//当前Node执行反转完毕,指向当前节点的指针后移
    }

    System.out.println("反转链表:" + nodes);

    return preNode;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58

执行结果:

初始链表:[{A,next :B}, {B,next :C}, {C,next :D}, {D,next :E}, {E,next :null}]
反转链表:[{A,next :null}, {B,next :A}, {C,next :B}, {D,next :C}, {E,next :D}]
反转之后新的头结点:{E,next :D}
  • 1
  • 2
  • 3

方式二:递归反转

public static void main(String[] args) {
    //初始化链表
    Node head = initList();

    //方式二:递归反转
    Node newHead = reverseByRecursion(head);
    System.out.println("反转之后新的头结点:"+newHead);
}

private static List<Node> nodes = new LinkedList<>();

/**
 * 初始化链表
 *
 * @return 头结点Head
 */
private static Node initList() {
    Node eNode = new Node("E", null);
    Node dNode = new Node("D", eNode);
    Node cNode = new Node("C", dNode);
    Node bNode = new Node("B", cNode);
    Node aNode = new Node("A", bNode);
    nodes.add(aNode);
    nodes.add(bNode);
    nodes.add(cNode);
    nodes.add(dNode);
    nodes.add(eNode);
    System.out.println("初始链表:" + nodes);
    return aNode;
}

/**
 * 方式二:递归反转
 *
 * @param head 头结点
 */
private static Node reverseByRecursion(Node head) {
    Node curNode = head;
    if (curNode == null || curNode.next == null) {
        //如果当前链表为空或链表只有一个节点Node 直接返回
        return curNode;
    }

    Node reverseHead = reverseByRecursion(curNode.next);//递归方法最后最后返回的即是链表的头结点
    curNode.next.next = curNode; //后继节点指针指向当前节点
    curNode.next = null; //当前节点指针置为空

    System.out.println("反转链表:" + nodes);

    return reverseHead;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51

执行结果:

初始链表:[{A,next :B}, {B,next :C}, {C,next :D}, {D,next :E}, {E,next :null}]

反转链表:[{A,next :B}, {B,next :C}, {C,next :D}, {D,next :null}, {E,next :D}]
反转链表:[{A,next :B}, {B,next :C}, {C,next :null}, {D,next :C}, {E,next :D}]
反转链表:[{A,next :B}, {B,next :null}, {C,next :B}, {D,next :C}, {E,next :D}]
反转链表:[{A,next :null}, {B,next :A}, {C,next :B}, {D,next :C}, {E,next :D}]
反转之后新的头结点:{E,next :D}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

上述结果将递归的每一步结果都打印出来了,这里递归实现的效率是没有方式一效率高的。

声明:本文内容由网友自发贡献,转载请注明出处:【wpsshop】
推荐阅读
相关标签
  

闽ICP备14008679号