反转链表 Reverse Linked List

2018-09-11 22:58:29

一、Reverse Linked List

问题描述:

反转链表 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

问题描述:

反转链表 Reverse Linked List

问题求解:

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

本题实际使用的思路是一种插入的思路,维护了三个指针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;
}
上一篇:lc面试准备:Reverse Linked List II


下一篇:LeetCode 92. 反转链表 II(Reverse Linked List II)