赞
踩
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 + "}"; } }
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; }
执行结果:
初始链表:[{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}
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; }
执行结果:
初始链表:[{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}
上述结果将递归的每一步结果都打印出来了,这里递归实现的效率是没有方式一效率高的。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。