Shulou(Shulou.com)06/01 Report--

This article is about how LeetCode flips a group of linked lists. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

Topic description:

Give you a linked list and flip it in a group of k nodes. Please return to the flipped list.

K is a positive integer whose value is less than or equal to the length of the linked list.

If the total number of nodes is not an integral multiple of k, keep the last remaining nodes in their original order.

Example:

Here is the linked list: 1-> 2-> 3-> 4-> 5

When k = 2, you should return: 2-> 1-> 4-> 3-> 5

When k = 3, you should return: 3-> 2-> 1-> 4-> 5

Description:

Your algorithm can only use constant extra space.

You can't just change the value inside the node, but you need to actually exchange the node.

Analysis of ideas:

Step decomposition:

The partition of the linked list is the flipped part + the part to be flipped + the unflipped part. To determine the scope of the flipped list before each flip, this must be determined through k this cycle to determine the need to record the front and successor of the flipped linked list. It is convenient to connect the flipped part with the unflipped part after the flip is completed. Initially, two variables pre and end,pre represent the precursor of the list to be flipped, and end represents the end of the list to be flipped through k this cycle. When end reaches the end, record the following next = end.next of the list to be flipped, then join the three parts of the list together, reset the pre and end pointers, and then enter the special case of the next cycle. When the length of the flip part is less than k, after positioning the end, end==null has reached the end, indicating that the topic has been completed and can be returned directly.

The time complexity is O (n ^ K), the best case is O (n), and the worst case is not O (n ^ 2) O.

The space complexity is O (1), and we don't take up any space except a few necessary node pointers.

Python implements # Definition for singly-linked list.

# class ListNode (object):

# def _ _ init__ (self, x):

# self.val = x

# self.next = None

Class Solution (object):

Def reverseKGroup (self, head, k):

Dummy = ListNode (0)

P = dummy

While True:

Count = k

Stack = []

Tmp = head

While count and tmp:

Stack.append (tmp)

Tmp = tmp.next

Count-= 1

# Note: the current location of tmp is Kull1.

# indicates that there are not enough linked lists left. Jump out of the loop.

If count:

P.next = head

Break

# Flip operation

While stack:

P.next = stack.pop ()

P = p.next

# connect with the remaining linked list

P.next = tmp

Head = tmp

Return dummy.next

Java implementation: / * *

* 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) {

If (head = = null | | head.next = = null) {

Return head

}

/ / define a fake node.

ListNode dummy=new ListNode (0)

/ / the next of the fake node points to head.

/ / dummy- > 1-> 2-> 3-> 4-> 5

Dummy.next=head

/ / initialize both pre and end point to dummy. Pre refers to the previous node of the head node of the linked list to be flipped each time. End refers to the tail node of the linked list to be flipped each time.

ListNode pre=dummy

ListNode end=dummy

While (end.nextframes null) {

/ / cycle k times to find the end of the linked list that needs to be flipped. Here, you need to determine whether end is equal to null in each loop, because if it is null, end.next will report a null pointer exception.

/ / dummy- > 1-> 2-> 3-> 4-> 5 if k is 2, cycle twice, end points to 2

For (int item0) becomes 2-> 1. Dummy- > 2-> 1

Pre.next=reverse (start)

/ / the head node changes to the end after flipping. Relink the broken list through. Next.

Start.next=next

/ / change pre to the previous node of the header node of the linked list to be flipped next time. That is start

Pre=start

/ / when flipping ends, set end to the previous node of the header node of the linked list to be flipped next time. That is start

End=start

}

Return dummy.next

}

/ / list flipping

/ / example: head:1- > 2-> 3-> 4

Public ListNode reverse (ListNode head) {

/ / if the single linked list is empty or has only one node, return the original single linked list directly

If (head = = null | | head.next = = null) {

Return head

}

/ / previous node pointer

ListNode preNode = null

/ / current node pointer

ListNode curNode = head

/ / next node pointer

ListNode nextNode = null

While (curNode! = null) {

NextNode = curNode.next;//nextNode points to the next node, saving the linked list after the current node.

CurNode.next=preNode;// points the current node next field to the previous node null

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.