自己解法
这个题是最近做过最难的一道链表题，链表题最关键的就是前置节点、后置节点的维护，这题真的被绕晕了，自己憋了一个晚上写了个巨长的逻辑，太乱了，先贴自己解法，思路是，K个一组进行切割，每组进行链表的反转操作。
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || k == 1) {
return head;
}
ListNode dummy = new ListNode(-1);
ListNode preNode = dummy;
preNode.next = head;
int i = 1;
while (head != null && head.next != null) {
head = head.next;
i++;
if (i == k) {
ListNode temp = head.next;
head.next = null;
List<ListNode> listNodes = reverseListNode(preNode.next);
preNode.next = listNodes.get(0);
preNode = listNodes.get(1);
head = temp;
preNode.next = head;
i = 1;
}
}
return dummy.next;
}
public List<ListNode> reverseListNode(ListNode head) {
ListNode tail = head;
ListNode preNode = null;
while (head != null) {
ListNode temp = head.next;
head.next = preNode;
preNode = head;
head = temp;
}
List<ListNode> res = new ArrayList<ListNode>(4);
res.add(preNode);
res.add(tail);
return res;
}
}
官方解法
下面贴上纯手打官方解法，就是维护要翻转的K个节点的前置节点pre，结尾节点end,有了这两个节点，可以很容易获取K个节点的开始节点start和K个节点的后置节点next。这样将反转后的节点拼到整个链表中就可以了，反转的时候有个小技巧，不要用head做后移，新起个变量，这样的话，这个head最后就是反转后链表的尾部，可以用来连接第3段链表。
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || k == 1) {
return head;
}
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy;
ListNode end = dummy;
while (end != null) {
for (int i = 0; i < k && end != null; i++) {
end = end.next;
}
if (end == null) {
break;
}
ListNode start = pre.next;
ListNode next = end.next;
end.next = null;
pre.next = reverseListNode(start);
// start不进行移动就是链表的结尾
start.next = next;
pre = start;
end = start;
}
return dummy.next;
}
public ListNode reverseListNode(ListNode head) {
ListNode pre = null;
// 不移动head指针，head指针会在反转后的最后一位
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
网友评论