Reverse Linked List II

今天是一道有关链表的题目，来自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.

解题思路及代码见阅读原文

回复0000查看更多题目

解题思路

首先，该题是Reverse Linked List的升级版，在Reverse Linked List一题中，是将链表整个翻转，比较简单：

• 一种方法是直接翻转，最后返回尾节点。如下

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

• 另一种方法是采用头插法，即先定义一个新的dummy节点，next指向链表的头结点；然后从head的next节点开始遍历链表，每一个遍历到的节点的next都指向dummy的next；同时dummy的next指向该节点。

然后，在该题中加入了翻转链表中间的m到n个节点，这里也可以采用头插法，不同的是这里的dummy节点是m-1个节点，即在遍历时将节点都查到这个节点后面。

需要注意的是，这里让需要生成一个局部变量dummy节点，为了防止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;        
    }
}

关注我
该公众号会每天推送常见面试题，包括解题思路是代码，希望对找工作的同学有所帮助

image