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

题目描述

给定一个链表，和一个正整数值X，请你把链表的节点按照每X个进行交换，然后返回交换后的链表。如果剩余的节点不足X个，则不用交换。

在之前我们做过的 中，是固定的两两交换，本题是它的升级版，交换的节点数，可动态传入。

示例：

解题思路：

相比固定的两两节点交换，本题我们首先还是先考虑把链表按照X的值，进行划分多个子链表，然后利用反转链表的方式，最后再拼接回原链表。

链表的题目一般对于算法思路上都比较容易理解，主要考验的还是编码的能力，本题看起来比较简单，实际对于编写的思路和技巧还是有一定要求的。

代码实现：

public class SwapListNode_02 {
       public static void main(String[] args) {
           SwapListNode_02 c = new SwapListNode_02();        ListNode n = new ListNode(1);        ListNode head = n;        for (int i = 2; i < 5; i++) {
               n.next = new ListNode(i);            n = n.next;        }        System.out.println(c.swapListNode(head, 2));    }    public ListNode swapListNode(ListNode head, int x) {
           ListNode dummy = new ListNode();        dummy.next = head;        ListNode pre = dummy;		//整体处理过程请看图解        while (head != null) {
               ListNode tail = pre;            for (int i = 0; i < x; i++) {
                   tail = tail.next;                if (tail == null) {
                       return dummy.next;                }            }            ListNode tailNext = tail.next;            ListNode[] rev = reverseList(head, tail);            head = rev[1];            tail = rev[0];            pre.next = head;            tail.next = tailNext;            pre = tail;            head = tailNext;        }        return dummy.next;    }    private ListNode[] reverseList(ListNode head, ListNode tail) {
           ListNode pre = tail.next;        ListNode cur = head;        while (pre != tail) {
               ListNode next = cur.next;            cur.next = pre;            pre = cur;            cur = next;        }        return new ListNode[]{
   head, tail};    }}

图解过程

初始化一个哑结点，和每个子链表的前一个节点

ListNode tail = pre;for (int i = 0; i < x; i++) {
       tail = tail.next;    if (tail == null) {
           return dummy.next;    }}

ListNode tailNext = tail.next;

进入反转链表的流程

ListNode[] rev = reverseList(head, tail);

ListNode pre = tail.next;ListNode cur = head;

ListNode next = cur.next;cur.next = pre;

pre = cur;cur = next;

第一次反转结束，重新反转流程，如下图，当第二次反转结果时，tail==pre，跳出循环，方法返回当前的head节点，和tail节点

交换head和tail节点

head = rev[1];tail = rev[0];

pre.next = head;tail.next = tailNext;

pre = tail;head = tailNext;

第一次遍历完成，最终结果如下

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