【原】LeetCode刷题实战25：K 个一组翻转链表

程序IT圈 2021-01-16

展开全文

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做K 个一组翻转链表，我们先来看题面：

https:///problems/reverse-nodes-in-k-group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

题意

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

样例

给你这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

题解

每k个节点进行一次反转，用两个指针记录k个区间的首尾节点，写一个reverse函数反转该局部内的节点指向，接着继续向后走，不停的取k个进行反转，如果不够k个就返回。具体代码如下：

import java.util.Scanner;

public class Main {
    //定义Node节点
    static class ListNode {
        public int val;
        public ListNode next = null;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        //1.获取输入信息
        Scanner scanner = new Scanner(System.in);
        String string = scanner.nextLine();
        int k = scanner.nextInt();
        String[] strings = string.split(" ");
        //2.创建头结点
        ListNode head = new ListNode(0);
        ListNode tail = head;
        //3.将输入的字符串变为链表节点
        for (String str : strings) {
            ListNode newNode = new ListNode(Integer.valueOf(str));
            tail.next = newNode;
            tail = tail.next;
        }
        head = head.next;
        //每k个反转链表
        ListNode node = reverseGroup(head, k);
        while(node!=null){
            System.out.print(node.val+" ");
            node = node.next;
        }
    }

    //不停地取k个进行翻转，如果不够k个，就直接返回,结束
    public static ListNode reverseGroup(ListNode head, int k) {
        if (head == null || head.next == null || k <= 1)
            return head;
        ListNode currentNode = head;
        //获取k个元素的首尾节点
        for (int count = 1; count < k; count++) {
            currentNode = currentNode.next;
            //不够K个则返回
            if(currentNode==null)
                return head;
        }
        ListNode next = currentNode.next;
        //对局部链表进行反转
        reverse(head,currentNode);
        head.next=reverseGroup(next,k);
        return currentNode;
    }

    //写一个头尾节点反转的局部函数
    public static ListNode reverse(ListNode head, ListNode tail) {
        if (head == null || head.next == null)
            return head;
        ListNode pre = null;
        ListNode next = null;
        while (pre != tail) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

}