题解 | #牛群链式排序#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode swapCows (ListNode head) {
        // 当队列为空或只有一个牛时，无需排序，直接返回
        if (head == null || head.next == null) {
            return head;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode prev = dummy; // 前驱节点
        ListNode curr = head; // 当前节点

        while (curr != null && curr.next != null) {
            ListNode nextNode = curr.next; // 下一个节点

            curr.next = nextNode.next; // 当前节点指向下下个节点
            nextNode.next = curr; // 下一个节点指向当前节点
            prev.next = nextNode; // 前驱节点指向下一个节点

            prev = curr; // 更新前驱节点为当前节点
            curr = curr.next; // 更新当前节点为下一个节点
        }

        return dummy.next; // 返回交换后的牛群的链表头节点
    }
}

本题知识点分析：

1.链表反转

2.数学模拟

本题解题思路分析：

1.当队列为空或只有一个牛时，无需排序，直接返回

2.分别保存前驱结点和当前节点

3.注意循环条件 while (curr != null && curr.next != null)

4.循环内代码按注释即可知晓

5.链表的题目画图，然后按图翻译就可以了，注意虚拟头结点问题，然后什么时候判空

本题使用编程语言: Java

如果您觉得本篇文章对您有帮助的话，可以点个赞支持一下，感谢~