牛客网算法——名企高频面试题143题（13)-白红宇

牛客网算法——名企高频面试题143题（13)

阅读量：400 次

发布时间：2019-03-04

本文共 2610 字，大约阅读时间需要 8 分钟。

????

?????????????????????????????????????????????????????????????

???????

??

?????????????????????????????

????????pre?curr??????????????????

??????????????????

?????????????????pre???????

??pre?curr??????????????????

???????pre????????????

???????????O(n)???????O(1)???????????????

????

public class ????II {    public class ListNode {        int val;        ListNode next;        public ListNode(int val) {            this.val = val;        }    }    public ListNode rever(ListNode head) {        if (head == null) {            return null;        }        ListNode pre = null;        ListNode curr = head;        while (curr != null) {            ListNode future = curr.next;            curr.next = pre;            pre = curr;            curr = future;        }        return pre;    }        public static void main(String[] args) {        // ????        ListNode s1 = new ListNode(1);        ListNode s2 = new ListNode(2);        ListNode s3 = new ListNode(3);        ListNode s4 = new ListNode(4);        s1.next = s2;        s2.next = s3;        s3.next = s4;        ListNode res = rever(s1);        while (res != null) {            System.out.println(res.val);            res = res.next;        }    }}

??????????

????????????????????????????????????????????

????dummy??????????????

???????????dummy?????????

????????pre?curr?????dummy?????????

????????????????????

?????????dummy????????????????????

????????O(n)???????O(1)???????

????

public class ????II {    public class ListNode {        int val;        ListNode next;        public ListNode(int val) {            this.val = val;        }    }    public ListNode rever1(ListNode head) {        if (head == null) {            return null;        }        ListNode dumy = new ListNode(0);        dumy.next = head;        ListNode pre = dumy;        ListNode curr = head;        while (curr.next != null) {            ListNode future = curr.next;            curr.next = future.next;            future.next = dumy.next;            pre.next = future;        }        return dumy.next;    }        public static void main(String[] args) {        // ????        ListNode s1 = new ListNode(1);        ListNode s2 = new ListNode(2);        ListNode s3 = new ListNode(3);        ListNode s4 = new ListNode(4);        s1.next = s2;        s2.next = s3;        s3.next = s4;        ListNode res = rever1(s1);        while (res != null) {            System.out.println(res.val);            res = res.next;        }    }}