[LeetCode-JAVA] Reverse Linked List I && II

浏览数：178 / 时间：2015年06月08日

题目I：

Reverse a singly linked list

思路：建立三个指针，一个用来维护链表头，另外两个再循环中，维护head的前一位和保存反转的后一位。

逐个反转，首先反转前两个，然后把前两个看成是一个，继续循环反转下去。

代码：

public class Solution {
    public ListNode reverseList(ListNode head) {
               ListNode dunmy = head;  //维护初始链表头，用于判断循环结束
        
        if(head == null || head.next == null)
            return head;
        ListNode pre = null;
        ListNode temp = null;
        while(dunmy.next != null){
            pre = head;              //记录当前节点
            head = dunmy.next;
            temp = head.next;   //保存next
            head.next = pre;
            dunmy.next = temp;
        }
        
        return head;
    }
}

题目II：

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.

思路：在I的基础上，没有太大的变化，找到开始的位置后，进行反转。

需要注意的是建立一个虚拟链表头，这样在连接的时候比较方便。

代码：

public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode pre = new ListNode(0);  //虚拟链表头
        pre.next = head;
        ListNode dunmy = pre;
        int len = n-m;
        while(m > 1){  // 找到反转的位置
            head = head.next;
            pre = pre.next;
            m--;
        }
        pre.next = reverse(head, len);  //进行连接
        
        return dunmy.next;
    }
    public ListNode reverse(ListNode head, int n){
        ListNode dunmy = head;
        
        if(head == null || head.next == null)
            return head;
        ListNode pre = null;
        ListNode temp = null;
        while(n > 0){
            pre = head;
            head = dunmy.next;
            temp = head.next;
            head.next = pre;
            dunmy.next = temp;
            n--;
        }
        
        return head;
    }
}