剑指offer-问题16

向右看齐 2022-05-10 17:38 125阅读 0赞

package offer;
    
    /**
     * offer interview 16
     */
    public class Test16 {
    
        public static class ListNode{
            int value;
            ListNode next;
    
            public ListNode(){
            }
    
            public ListNode(int value){
                this.value = value;
                this.next = null;
            }
    
        }
    
    
        //method 1
        public static ListNode reverseList(ListNode head){
            ListNode root = new ListNode();
            root.next = null;
    
            ListNode next;
    
            while (head != null){
                next = head.next;
    
                head.next = root.next;
                root.next = head;
    
                head = next;
            }
    
            return root.next;
    
        }
    
        //method 2
        public static ListNode reverseList2(ListNode head){
            ListNode reverseHead = null;
            ListNode curr = head;
            ListNode prev = null;
            ListNode next;
    
            while (curr != null){
                reverseHead = curr;
                next = curr.next;
    
                curr.next = prev;
                prev = curr;
                curr = next;
            }
    
            return reverseHead;
        }
    
    
        public static void printList(ListNode head){
            while (head != null){
                System.out.print(head.value + "->");
                head =  head.next;
            }
            System.out.println("null");
        }
    
        public static void main(String[] args){
            ListNode head = new ListNode(1);
            head.next = new ListNode(2);
            head.next.next = new ListNode(3);
            head.next.next.next = new ListNode(4);
            head.next.next.next.next = new ListNode(5);
            head.next.next.next.next.next = new ListNode(6);
            head.next.next.next.next.next.next = new ListNode(7);
            head.next.next.next.next.next.next.next = new ListNode(8);
            head.next.next.next.next.next.next.next.next = new ListNode(9);
    
            printList(head);
            head = reverseList(head);
            printList(head);
    
            System.out.println("========");
            head = reverseList2(head);
            printList(head);
        }
    
    }