題目：

給出一個鏈表，每 k 個節點一組進行翻轉，并返回翻轉后的鏈表。

k 是一個正整數，它的值小于或等于鏈表的長度。如果節點總數不是 k 的整數倍，那么將最后剩余節點保持原有順序。

示例 :

給定這個鏈表：1->2->3->4->5當 k = 2 時，應當返回: 2->1->4->3->5當 k = 3 時，應當返回: 3->2->1->4->5

說明 :

你的算法只能使用常數的額外空間。
你不能只是單純的改變節點內部的值，而是需要實際的進行節點交換。

package com.letcode.list;class ListNode{int val;ListNode next;ListNode(int x){val = x;} }/* * 給定這個鏈表：1->2->3->4->5 * 當 k = 2 時，應當返回: 2->1->4->3->5 * 當 k = 3 時，應當返回: 3->2->1->4->5 */ public class ReverseKNodes {ListNode newTail=null;public static void main(String[] args) {System.out.println("main...");ListNode a = new ListNode(1);ListNode b = new ListNode(2);ListNode c = new ListNode(3);ListNode d = new ListNode(4);ListNode e = new ListNode(5);a.next = b;b.next = c;c.next = d;d.next = e;ReverseKNodes reverseKNodes = new ReverseKNodes();ListNode newHead = reverseKNodes.reverseKGroup(a, 4);while(null != newHead){System.out.println(newHead.val);newHead = newHead.next;}}public ListNode reverseKGroup(ListNode head, int k) {// k肯定是大于等于2的，這樣反轉鏈表才有意義，所以當k<=1時,直接返還if(head==null||k<=1){return head;}ListNode newHead=new ListNode(-1);//每k個反轉鏈表的前置頭結點newHead.next=head;ListNode tail=head;//每一組鏈表的尾結點head=newHead;int n=1;System.out.println(tail.val);while(tail!=null){if(n%k==0){// n%k==0 表示每k個節點進行一次反轉newTail=newHead.next;//新的尾結點System.out.println("newTail:"+newTail.val);reverse(newHead,tail);newHead=newTail;//上一組的尾結點做下一組的頭結點tail=newTail;}tail=tail.next;n++;}return head.next;}// -1(n) 1 2 3 4(t) 5public void reverse(ListNode head,ListNode tail){//head為頭結點，不帶有任何參數，并且能調用這個函數，說明至少有兩個及以上的節點需要逆置，//所以第一次的cur代表第二個元素，不會空指針ListNode cur=head.next.next;//準備前插的元素 2ListNode curNext=cur.next;//前插的下一個元素，可能為空 3//while(cur!=null){while(true){//不需要判斷cur和curNext為空的情況，while里面可以直接寫true//因為tail是本次逆置部分的最后一個元素，cur前插肯定會遇見它cur.next=head.next;//連接后面 2 1head.next=cur;//連接頭結點 -1 2 1if(cur==tail){newTail.next=curNext;//將新鏈表的尾部與下一次k鏈的第一個元素進行連接break;}cur=curNext;//下一個需要頭插的元素 4curNext=cur.next; // 5}} }

?

?

?

總結

以上是生活随笔為你收集整理的常考数据结构与算法:每k个节点反转链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。