92.反转链表2

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

自己的理解：需要反转的链表的尾巴节点和它的next还有头结点和它的pre给找到，然后先断开前驱和后继，对需要反转的部分进行反转。然后连上前驱和后继。

自己的代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode HeadPre=new ListNode(-999);
        ListNode Head=new ListNode(-999);

        ListNode Final=new ListNode(-999);
        ListNode FinalNext=new ListNode(-999);
        //先找最后一个元素和最后一个元素之后的元素
        Final=head;
        //找到最后一个元素 以及最后一个元素之后的元素
        for(int i=0;i<n-1;i++)
        {
            Final=Final.next;
        }
//        System.out.println(Final.val);
        FinalNext=Final.next;
        Final.next=null;

        //找到第一个元素和前面的元素
        if(m<2)
        {
            HeadPre.next=head;
            Head=HeadPre.next;//需要翻转的头结点
            HeadPre.next=null;//先保存这个翻转之前的节点
        }
        else{
            HeadPre=head;
            for(int i=0;i<m-1-1;i++)
            {
                HeadPre=HeadPre.next;
            }
//        System.out.println(HeadPre.val);
            Head=HeadPre.next;//需要翻转的头结点
            HeadPre.next=null;//先保存这个翻转之前的节点
        }

//        System.out.println(head.val);

        ListNode prev = FinalNext;
        ListNode curr = Head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }

        if (m<2)
        {
            head=prev;
        }
        else
        {
            HeadPre.next=prev;
        }
        return head;

    }
}

专业的题解：

92.反转链表2

public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode res = new ListNode(0);
        res.next = head;
        ListNode node = res;
        //找到需要反转的那一段的上一个节点。
        for (int i = 1; i < m; i++) {
            node = node.next;
        }
        //node.next就是需要反转的这段的起点。
        ListNode nextHead = node.next;
        ListNode next = null;
        ListNode pre = null;
        //反转m到n这一段
        for (int i = m; i <= n; i++) {
            next = nextHead.next;
            nextHead.next = pre;
            pre = nextHead;
            nextHead = next;
        }
        //将反转的起点的next指向next。
        node.next.next = next;
        //需要反转的那一段的上一个节点的next节点指向反转后链表的头结点
        node.next = pre;
        return res.next;
    }

相关推荐