2018-09-11 22:58:29

一、Reverse Linked List

问题描述：

问题求解：

解法一：Iteratively，不断执行插入操作。

public ListNode reverseList(ListNode head) {        if (head == null) return null;        ListNode dummy = new ListNode(-1);        dummy.next = head;        ListNode cur = head;        ListNode then = null;        while (cur.next != null) {            then = cur.next;            cur.next = then.next;            then.next = dummy.next;            dummy.next = then;        }        return dummy.next;    }

解法二：Recursively，不断向newHead前面加入新的节点

public ListNode reverseList(ListNode head) {        /* recursive solution */        return reverseListInt(head, null);    }    private ListNode reverseListInt(ListNode head, ListNode newHead) {        if (head == null)        return newHead;        ListNode next = head.next;        head.next = newHead;        return reverseListInt(next, head);    }

 

二、Reverse Linked List II

问题描述：

问题求解：

反转链表一直是一个很经典的问题，本题中其实是最经典的全局反转的一个改进和加深，本题的求解思路完全可以套用到全局反转中。

本题实际使用的思路是一种插入的思路，维护了三个指针prev，cur，then。

prev ： 初始位置的前一个位置，始终不变，后续就是在prev后进行插入；

cur ： 不断迭代，指向需要插入的节点的前一个位置；

then ： cur的下一个节点，是每次需要进行插入的节点，同时需要不断迭代。

public ListNode reverseBetween(ListNode head, int m, int n) {        ListNode dummy = new ListNode(-1);        dummy.next = head;        ListNode prev = dummy;        ListNode cur = dummy;        ListNode then = null;        for (int i = 0; i < m; i++) {            prev = cur;            cur = cur.next;            then = cur.next;        }        for (int i = 0; i < n - m; i++) {            cur.next = then.next;            then.next = prev.next;            prev.next = then;            then = cur.next;        }        return dummy.next;    }