练习：java链表翻转

￡神魔★判官ぃ 2023-01-13 05:47 96阅读 0赞

/** * @description ：链表翻转 * Created by @author YongliangWang on 2021/4/2 15:23 */
    public class DataStructureTest { 
        public static void main(String[] args) { 
            Node n1 = new Node("L");
            Node n2 = new Node("I");
            Node n3 = new Node("N");
            Node n4 = new Node("K");
            n1.next = n2;
            n2.next = n3;
            n3.next = n4;
            Node n = n1;
            while (null != n) { 
                System.out.println(n.toString());
                n = n.next;
            }
            System.out.println("\n---reverse------\n");
            n = reverseLink(n1);
            while (n != null) { 
                System.out.println(n.toString());
                n = n.next;
            }
        }
    
        public static class Node { 
            Object data;//数据域
            Node next;//指针域
    
            public Node(Object data) { 
                this.data = data;
            }
    
            @Override
            public String toString() { 
                return "Node { data = " + data + '}';
            }
        }
    
        private static Node reverseLink(Node head) { 
            //单链表为空或单一节点时，直接返回原单链表即可
            if (head == null || head.next == null) { 
                return head;
            }
            Node prevNode = null;//前一个节点指针
            Node currNode = head;//当前节点指针
            Node nextNode = null;//下一个节点指针
            while (currNode != null) { 
                nextNode = currNode.next;//nextNode 指向下一个节点
                currNode.next = prevNode;//将当前节点next域指向前一个节点
                prevNode = currNode;//preNode 指针向后移动
                currNode = nextNode;//curNode指针向后移动
            }
            return prevNode;
        }
    }

打印结果如下：

Node {  data = L}
    Node {  data = I}
    Node {  data = N}
    Node {  data = K}
    
    ---reverse------
    
    Node {  data = K}
    Node {  data = N}
    Node {  data = I}
    Node {  data = L}