数据结构与算法之反转单向链表和双向链表

野性酷女 2021-12-24 06:15 325阅读 0赞

# 数据结构与算法之反转单向链表和双向链表 #

--------------------

## 目录 ##

1.  反转单向链表和双向链表

--------------------

### 1. 反转单向链表和双向链表 ###

1.  题目描述  
    ![在这里插入图片描述][20190626202846455.png]
2.  代码实现

public class Code_ReverseList {
        
    
        public static class Node {
        
            public int value;
            public Node next;
    
            public Node(int data) {
        
                this.value = data;
            }
        }
    
        public static Node reverseList(Node head) {
        
            Node pre = null;
            Node next = null;
            while (head != null) {
        
                next = head.next;
                head.next = pre;
                pre = head;
                head = next;
            }
            return pre;
        }
    
        public static class DoubleNode {
        
            public int value;
            public DoubleNode last;
            public DoubleNode next;
    
            public DoubleNode(int data) {
        
                this.value = data;
            }
        }
    
        public static DoubleNode reverseList(DoubleNode head) {
        
            DoubleNode pre = null;
            DoubleNode next = null;
            while (head != null) {
        
                next = head.next;
                head.next = pre;
                head.last = next;
                pre = head;
                head = next;
            }
            return pre;
        }
    
        public static void printLinkedList(Node head) {
        
            System.out.print("Linked List: ");
            while (head != null) {
        
                System.out.print(head.value + " ");
                head = head.next;
            }
            System.out.println();
        }
    
        public static void printDoubleLinkedList(DoubleNode head) {
        
            System.out.print("Double Linked List: ");
            DoubleNode end = null;
            while (head != null) {
        
                System.out.print(head.value + " ");
                end = head;
                head = head.next;
            }
            System.out.print("| ");
            while (end != null) {
        
                System.out.print(end.value + " ");
                end = end.last;
            }
            System.out.println();
        }
    
        public static void main(String[] args) {
        
            Node head1 = new Node(1);
            head1.next = new Node(2);
            head1.next.next = new Node(3);
            printLinkedList(head1);
            head1 = reverseList(head1);
            printLinkedList(head1);
    
            DoubleNode head2 = new DoubleNode(1);
            head2.next = new DoubleNode(2);
            head2.next.last = head2;
            head2.next.next = new DoubleNode(3);
            head2.next.next.last = head2.next;
            head2.next.next.next = new DoubleNode(4);
            head2.next.next.next.last = head2.next.next;
            printDoubleLinkedList(head2);
            printDoubleLinkedList(reverseList(head2));
    
        }
    }

1.  编译结果  
    ![在这里插入图片描述][20190626203006450.png]

[20190626202846455.png]: /images/20211223/28a8e8818ff6451cb20fd66d24777c14.png
[20190626203006450.png]: /images/20211223/f2126093336f423383d6b4e32d289691.png