链接：https://www.nowcoder.com/questionTerminal/25ba57f0f5394efe9c2fff2a164e26e4
来源：牛客网
给你一个链表，每 k 个节点一组进行翻转，请返回翻转后的链表。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例 :
给定这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
输入描述:
第一行：依次输入链表中的各个元素，以"#"结束
第二行：每组数量k
输出描述:
处理后的链表中的各个元素，以"->"连接
示例1
输入
1 2 3 4 5 #
2
输出
2->1->4->3->5
示例2
输入
1 2 3 4 5 #
3
输出
3->2->1->4->5
import java.util.*;
class ListNode{
int val;
ListNode next = null;
ListNode(int val){
this.val = val;
}
}
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while (sc.hasNextLine()){
String[] str = sc.nextLine().split(" ");
int k = Integer.valueOf(sc.nextLine());
ListNode pre = new ListNode(Integer.valueOf(str[0]));
ListNode head = pre;
for (int i=1;i<str.length-1;i++){
ListNode node = new ListNode(Integer.valueOf(str[i]));
pre.next = node;
pre = node;
}
pre.next = null;
head = reverse(head, k);
while (head != null){
if(head.next!=null){
System.out.print(head.val+"->");
}else{
System.out.print(head.val);
}
head = head.next;
}
}
}
public static ListNode reverse(ListNode head, int k){
ListNode tmp = head;
for (int i=1;i<k&&tmp!=null;i++)
tmp = tmp.next;
if (tmp == null) return head;
ListNode Lhead = tmp.next;
tmp.next = null;
ListNode newHead = revK(head);
ListNode newLHead = reverse(Lhead, k);
head.next = newLHead;
return newHead;
}
public static ListNode revK(ListNode head){
ListNode tmp = null, pre = null;
while (head != null){
tmp = head.next;
head.next = pre;
pre = head;
head = tmp;
}
return pre;
}
}
网友评论