給你一個鏈表，每 k 個節點一組進行翻轉，請你回傳翻轉后的鏈表， k 是一個正整數，它的值小于或等于鏈表的長度， 如果節點總數不是 k 的整數倍，那么請將最后剩余的節點保持原有順序， 示例： 給你這個鏈表：1->2->3->4->5 當 k = 2 時，應當回傳: 2->1->4->3->5 當 k = 3 時，應當回傳: 3->2->1->4->5 鏈接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group
思路：比如1->2->3->4->5，k=3；
先找到3和4的位置，然后斷開，在把3前面的反轉（這時候知道1和3節點）
把4后面的遞回
把3節點和后面的節點連接起來
/**** * K 個一組翻轉鏈表 * pre k=3時 * 1->2->3->4->5->6->7->8 * after: * 3->2->1->6->5->4->7->8 ** */ public static ListNode reverseKGroup(ListNode head, int k) { ListNode temp = head; // 先用temp找到3的位置，不足，就回傳head不反轉 for(int i=1;i<k && temp!=null;i++){ temp=temp.next; } if (temp == null) return head; // 用t2記錄記錄4的位置，把三四斷開 ListNode t2 = temp.next; temp.next=null; // 反轉前部分，頭部設定為newHead，此時head在3的位置了 ListNode newHead = reListNode(head); // 把1-2-3與后面的連接起來，后面的繼續遞回：head.next=reverseKGroup(t2,k); head.next=reverseKGroup(t2,k); return newHead; }
具體代碼
public class ListNode { int value; public ListNode(int value){ this.value=https://www.cnblogs.com/tk55/p/value; } ListNode next =null; } public class TestListNode { public static void main(String[] args) { ListNode head = new ListNode(1); head.next=new ListNode(2); head.next.next= new ListNode(3); head.next.next.next=new ListNode(4); head.next.next.next.next=new ListNode(5); head.next.next.next.next.next=new ListNode(6); head.next.next.next.next.next.next=new ListNode(7); head.next.next.next.next.next.next.next=new ListNode(8); System.out.println("pre"); printListNode(head); ListNode after = reverseKGroup(head,3); System.out.println("after:"); printListNode(after); } /**** * K 個一組翻轉鏈表 * pre k=3時 * 1->2->3->4->5->6->7->8 * after: * 3->2->1->6->5->4->7->8 ** */ public static ListNode reverseKGroup(ListNode head, int k) { ListNode temp = head; // 先用temp找到3的位置，不足，就回傳head不反轉 for(int i=1;i<k && temp!=null;i++){ temp=temp.next; } if (temp == null) return head; // 用t2記錄記錄4的位置，把三四斷開 ListNode t2 = temp.next; temp.next=null; // 反轉前部分，頭部設定為newHead，此時head在3的位置了 ListNode newHead = reListNode(head); // 把1-2-3與后面的連接起來，后面的繼續遞回：head.next=reverseKGroup(t2,k); head.next=reverseKGroup(t2,k); return newHead; } private static ListNode reListNode(ListNode head){ ListNode next=null; ListNode pre=null; while (head!=null){ next=head.next; head.next=pre; pre=head; head=next; } return pre; } private static void printListNode(ListNode node){ ListNode temp=node; while (temp.next!=null){ System.out.print(temp.value+"->"); temp=temp.next; } if (temp!=null){ System.out.println(temp.value); } } }View Code
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/5284.html
標籤：其他