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;
}