本文共 1229 字，大约阅读时间需要 4 分钟。

链接：

大意：

给定一个链表head，以及一个整数区间[m,n]，其中1 <= m <= n <= length of list。要求对链表的第m到第n个元素进行逆置。

思路：

将链表分为三段：

第一段：1 ~ m - 1。找到第一段的最后一个节点，用于和第二段逆置后的首节点进行相连

第二段：m ~ n。使用头插法重新构造第二段链表，并在最后记录第三段的首节点，用于和第二段逆置后的尾节点进行连接

第三段：n + 1 ~ length。

代码：

/** * 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) {        if (m == n)            return head;        ListNode pre = null, cur = head; // pre为第一段的尾节点，cur为当前遍历到的节点        int i = 1;        // 获取到第一段的尾节点        while (i < m) {            pre = cur;            cur = cur.next;            i++;        }        // 对第二段进行头插法重新构造链表 跳出循环后cur为第三段的首节点        ListNode head2 = new ListNode(0), newTail = cur; // newTail为第二段转置后的尾节点  用于与第三段相连        while (i <= n) {            ListNode tmp = cur.next;            cur.next = head2.next;            head2.next = cur;            cur = tmp;            i++;        }        newTail.next = cur; // 连接第二段和第三段        if (pre == null) { // 意味着m==1            return head2.next;        } else {            pre.next = head2.next; // 连接第一段和第二段            return head;        }    }}

结果：

结论：

做链表题，主要就是逻辑思路。 

转载地址：http://vtesi.baihongyu.com/