LeetCode刷题实战25:K 个一组翻转链表
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
今天和大家聊的问题叫做K 个一组翻转链表,我们先来看题面:
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节点
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;
}
}
上期推文: