?LeetCode刷題實戰(zhàn)25：K 個一組翻轉(zhuǎn)鏈表
算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎知識和業(yè)務邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選 ！
今天和大家聊的問題叫做K 個一組翻轉(zhuǎn)鏈表，我們先來看題面：
https://leetcode-cn.com/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.
題意
樣例
給你這個鏈表：1->2->3->4->5
當?k?= 2 時，應當返回: 2->1->4->3->5
當?k?= 3 時，應當返回: 3->2->1->4->5
題解
import java.util.Scanner;
public?class?Main?{
????//定義Node節(jié)點
????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.創(chuàng)建頭結(jié)點
????????ListNode head = new?ListNode(0);
????????ListNode tail = head;
????????//3.將輸入的字符串變?yōu)殒湵砉?jié)點
????????for?(String str : strings) {
????????????ListNode newNode = new?ListNode(Integer.valueOf(str));
????????????tail.next = newNode;
????????????tail = tail.next;
????????}
????????head = head.next;
????????//每k個反轉(zhuǎn)鏈表
????????ListNode node = reverseGroup(head, k);
????????while(node!=null){
????????????System.out.print(node.val+" ");
????????????node = node.next;
????????}
????}
????//不停地取k個進行翻轉(zhuǎn)，如果不夠k個，就直接返回,結(jié)束
????public?static?ListNode reverseGroup(ListNode head, int?k) {
????????if?(head == null?|| head.next == null?|| k <= 1)
????????????return?head;
????????ListNode currentNode = head;
????????//獲取k個元素的首尾節(jié)點
????????for?(int?count = 1; count < k; count++) {
????????????currentNode = currentNode.next;
????????????//不夠K個則返回
????????????if(currentNode==null)
????????????????return?head;
????????}
????????ListNode next = currentNode.next;
????????//對局部鏈表進行反轉(zhuǎn)
????????reverse(head,currentNode);
????????head.next=reverseGroup(next,k);
????????return?currentNode;
????}
????//寫一個頭尾節(jié)點反轉(zhuǎn)的局部函數(shù)
????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;
????}
}
上期推文：