Reverse Linked List II

今天是一道有關(guān)鏈表的題目，來自LeetCode伶丐，難度為Medium明吩，Acceptance為26.6%皆串。

題目如下

Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:1 ≤ *m* ≤ *n* ≤ length of list.

解題思路及代碼見閱讀原文

回復(fù)0000查看更多題目

解題思路

首先，該題是Reverse Linked List的升級(jí)版追驴，在Reverse Linked List一題中械哟，是將鏈表整個(gè)翻轉(zhuǎn)，比較簡(jiǎn)單：

• 一種方法是直接翻轉(zhuǎn)殿雪，最后返回尾節(jié)點(diǎn)暇咆。如下

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseList(ListNode head) {
        
        if(null == head)
            return null;
        
        ListNode cur = head, pre = null, next = null;
        
        while(cur != null){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

• 另一種方法是采用頭插法，即先定義一個(gè)新的dummy節(jié)點(diǎn)丙曙，next指向鏈表的頭結(jié)點(diǎn)爸业；然后從head的next節(jié)點(diǎn)開始遍歷鏈表，每一個(gè)遍歷到的節(jié)點(diǎn)的next都指向dummy的next亏镰；同時(shí)dummy的next指向該節(jié)點(diǎn)扯旷。

然后，在該題中加入了翻轉(zhuǎn)鏈表中間的m到n個(gè)節(jié)點(diǎn)索抓，這里也可以采用頭插法钧忽，不同的是這里的dummy節(jié)點(diǎn)是m-1個(gè)節(jié)點(diǎn)，即在遍歷時(shí)將節(jié)點(diǎn)都查到這個(gè)節(jié)點(diǎn)后面逼肯。

需要注意的是耸黑，這里讓需要生成一個(gè)局部變量dummy節(jié)點(diǎn)，為了防止m=1的情況篮幢。

代碼如下

Java版

/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param ListNode head is the head of the linked list 
     * @oaram m and n
     * @return: The head of the reversed ListNode
     */
    public ListNode reverseBetween(ListNode head, int m , int n) {
        // write your code
        if(null == head)
            return null;
        ListNode dummy= new ListNode(0);
        dummy.next = head;
        ListNode prev = newHead;
        for(int i = 0; i < m - 1; i++) {
            prev = prev.next;
        }
        ListNode first = prev.next, cur = head;
        for(int i = 0; i < m; i++) {
            cur = cur.next;
        }
        for(int i = 0; i < n - m; i++) {
            first.next = cur.next;
            cur.next = prev.next;
            prev.next = cur;
            cur = first.next;
        }
        return dummy.next;        
    }
}

關(guān)注我
該公眾號(hào)會(huì)每天推送常見面試題大刊，包括解題思路是代碼，希望對(duì)找工作的同學(xué)有所幫助

image