leetcode第25題(困難)問題描述
給你一個鏈表，每?k?個節點一組進行翻轉，請你返回翻轉后的鏈表。
k?是一個正整數，它的值小于或等于鏈表的長度。
如果節點總數不是?k?的整數倍，那么請將最后剩余的節點保持原有順序。
示例：
給你這個鏈表：1->2->3->4->5
當?k?= 2 時，應當返回: 2->1->4->3->5
當?k?= 3 時，應當返回: 3->2->1->4->5解題思路
整體思路是將原鏈表分成p(p=n個節點 / k)段(邏輯上的分)，每段都有一個頭節點和一個尾節點。
第一步先遍歷一次整個原鏈表，當每一組節點滿足有k個節點時，標記當前組的頭節點和尾節點。
第二步翻轉鏈表，改變每組的頭節點和尾節點的引用。返回第一組的頭節點即可。
這樣的時間復雜度就是 O(n)+O(n/k)
示例代碼(java)/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
return begin(head,k);
}
public static ListNode th;
/**
* 拼接反轉的鏈表
* @param listNode
* @param k
* @return
*/
public static ListNode begin(ListNode listNode,int k){
if(k==1){
return listNode;
}
th=listNode;
LinkedList ov=new LinkedList();
while(th!=null){
ListNode head=th;
ListNode tail=reversal(th,k);
ov.addLast(new HeadTail(tail,head));
}
if(ov.size()==0){
return null;
}else{
HeadTail headTail=ov.removeFirst();
ListNode head=headTail.head;
ListNode tail=headTail.tail;
while(ov.size()>0){
headTail=ov.removeFirst();
tail.next=headTail.head;
tail=headTail.tail;
}
return head;
}
}
/**
* 反轉鏈表
* @param node
* @param k
* @return
*/
public static ListNode reversal(ListNode node,int k){
ListNode p=null;
ListNode n;
int i=0;
while(node.next!=null){
n=node.next;
node.next=p;
p=node;
node=n;
i++;
if(i==k-1){
break;
}
}
th=node.next;
node.next=p;
if(i
node=reversal2(node,k);
}
return node;
}
/**
* 反轉鏈表
* @param node
* @param k
* @return
*/
public static ListNode reversal2(ListNode node,int k){
ListNode p=null;
ListNode n;
while(node.next!=null){
n=node.next;
node.next=p;
p=node;
node=n;
}
node.next=p;
return node;
}
public static class HeadTail {
ListNode head;
ListNode tail;
public HeadTail(ListNode head,ListNode tail){
this.head=head;
this.tail=tail;
}
}
}
