algorithm/Week_01/id_118/leetcode_25_118.java at master · cloudrib/algorithm · GitHub

History

79 lines (65 loc) · 2.23 KB

Raw

/**

* https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

* Definition for singly-linked list.

* public class ListNode {

* int val;

* ListNode next;

* ListNode(int x) { val = x; }

* }

class Solution {

public ListNode reverseKGroup(ListNode head, int k) {

// 1. 边界值处理：空指针、一个节点、k小于等于1

if(head==null || head.next==null || k<=1){

return head;

}

// 2. 加哨兵节点

ListNode guard = new ListNode(0);

guard.next = head;

// 3. 左侧已翻转完链表的尾节点，并将其指向 null，避免产生环

ListNode left = guard;

left.next = null;

// 4. head 不为 null，则持续翻转

while(head!=null){

// 判断剩下的部分是否还有 k 个节点能翻转

if(!hasEnoughNode(head,k)){

break;

}

// 把头结点提拉出来，作为翻转部分的第一个节点

ListNode new_tail = head;// 新翻转链表的尾节点

ListNode new_head = head;// 新翻转链表的头结点

head = head.next;

new_tail.next = null;// 这是为了避免误操作搞出环来

// 然后再找k-1个节点出来，插到链表头

int count = k-1;

while(count!=0){

ListNode tmp = head;

head = head.next;

tmp.next = new_head;

new_head = tmp;

count--;

}

// 左边的链表，和新翻转的链表串起来

left.next = new_head;

// 移动尾巴

left = new_tail;

}

// 5.最后再把没反转的部分给链上

left.next = head;

// 6. 返回

return guard.next;

}

// 判断后面是否还有足够的节点可以反转。

boolean hasEnoughNode(ListNode head,int k){

ListNode tmp = head;

while(k!=0){

if(tmp == null){

return false;

}

tmp=tmp.next;

k--;

}

return true;

}

algorithm/Week_01/id_118/leetcode_25_118.java at master · cloudrib/algorithm · GitHub

Expand file tree

Breadcrumbs

leetcode_25_118.java

Latest commit

History

Breadcrumbs

leetcode_25_118.java

File metadata and controls