Swap Nodes in Pairs and Reverse Nodes in K Groups

Let’s continue…

Problem Statement:

Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

Example:

Given 1->2->3->4, you should return the list as 2->1->4->3.

Note:

Your algorithm should use only constant extra space.
You may not modify the values in the list’s nodes, only nodes itself may be changed.

Solution One: Regular Swap

This is not a hard problem. The only thing you need to consider when swapping two nodes is that you have to consider the first pair, because there is no Node before the first node.

A typical solution to solve eliminate this difference is to add a dummy node before head. So we can swap the rest of node using the same strategy. Look at the picture below, that’s the procedure.

24_6

We first create a new pointer, and move this pointer forward through one iteration. We also create another two pointers, which represent the two elements which we want to swap. The swap process is shown in the picture above.

Time Complexity: O(n)

Space Complexity: O(1)

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode* swapPairs(ListNode* head) {
	ListNode* dummy = new ListNode(0);
	dummy->next = head;
	ListNode* p = dummy;
	while(p->next&&p->next->next){
	ListNode* p1 = p->next;
	ListNode* p2 = p->next->next;
	p->next = p2;
	p1->next = p2->next;
	p2->next = p1;
	p = p1;
	}
	return dummy->next;
	}
	};

view raw

SwapNodesinPairs_RSwap.cpp

hosted with ❤ by GitHub

Solution Two: Recursion

We can use recursion to solve this problem. Basically, we can divide the swap process into different sub problems. When we swap head with its following element, let’s say p. We always know, after swapping these two elements, p->next = head, the only thing we need to calculate is head->next = ? So we can recursively call the function and pass a new head head->next->next to the recursion function.

The base case is when head or head->next is NULL, which means we reach the end.

Time Complexity: O(n)

Space Complexity: O(n)

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode* swapPairs(ListNode* head) {
	if(head == NULL \|\| head->next == NULL){
	return head;
	}
	ListNode *p = head->next;
	head->next = swapPairs(head->next->next);
	p->next = head;
	return p;
	}
	};

view raw

SwapNodesinPairs_Recursion.cpp

hosted with ❤ by GitHub

Problem Statement:

Reverse Nodes in K-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Example:

Given this linked list: 1->2->3->4->5

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

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

Note:

Only constant extra memory is allowed.
You may not alter the values in the list’s nodes, only nodes itself may be changed.

Solution One: Recursion

This problem can be considered as a harder version of previous problem. However, we can still utilize the power of recursion. The general idea here is first we extract K elements, we reverse them, then we continue to extract the next K elements, reverse them… until we reverse all the subsets of the elements… We connect each of them together during the recursion call.

We defined a reverse function, which accept a link list and reverse the order, and then return the reversed link list. Let’s look at the code…

Time Complexity: O(n) I believe here we only need to touch each element once.

Space Complexity: O(n)

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	//Reverse elements in link list
	ListNode* reverseList(ListNode* head){
	ListNode* currentNode = NULL;
	//Current Node which stores the reversed head
	while(head!=NULL){
	ListNode* next = head->next;
	head->next = currentNode;
	currentNode = head;
	head = next;
	}
	return currentNode;

	}
	ListNode* reverseKGroup(ListNode* head, int k) {
	if(head == NULL)
	return NULL;

	ListNode* pointer = head;
	//Get K elements out of group
	int i = k;
	while(i – 1 > 0){
	pointer = pointer->next;
	if(pointer == NULL)
	return head;
	i–;
	}
	//Save pointer-> next, this is the next head
	ListNode* tempNode = pointer->next;
	//Break the K elements from the whole link list
	pointer->next = NULL;
	ListNode* currentNode = reverseList(head);
	//Recursively sort the next K elements
	head->next = reverseKGroup(tempNode,k);
	return currentNode;
	}
	};

view raw

ReverseNodesKGroup_Recursion.cpp

hosted with ❤ by GitHub

Solution Two: Regular Swap

We can also solve this problem by using regular swap method. Just like the method from the previous question. However, it will involve the movement of three pointers, so we need to break down the whole procedure into different steps, and analyze each step one by one.

The general idea is we take the first K elements, reverse them and then put them back to the original link list. Then we iterate to the next K elements, do the same operation, until we can not find K elements.

First thing we need to do is to create several pointers to keep track of the process.

The sub_head pointer is the head of the sub string (with K elements in it);

dummy should be the same as the previous problem;

tail always point to the last element of the previous reversed sub list, at first, it should point to dummy;

toNull is the pointer which points to the last element of the current sub list, it will break the sub list from the link list, currently, it points to the head Node.

25_2

The next thing we need to do is create a while loop and move toNull pointer to the last element of sub list. Note: if we do not have K elements in the sub list, we return the head.

25_3

Then we break the sub list from the original list. We first create a temp pointer to record the head of the remaining list. Then we set toNull->next = NULL;

25_4

After that, we call the reverse function, just like solution one, we save the reversed head address to a new new_sub_head pointer.

25_5

So the next step is a little trickier, we need to connect the reversed sub list to the original list.We first make the tail->next = new_sub_head (look at the picture above), then we move tail to sub_head, because this is the new tail position. Next we move the sub_head pointer to the temp pointer, which means the start position of next sub list, we also need to move toNull to temp position.

25_6

25_7

You can see from the above picture, all pointers (tail, sub_head, and toNull) are on the right location, which means we can do the next iteration. Let’s look at the code.

Time Complexity: O(2* n) which is O(n)

Space Complexity: O(1)

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode* reverse(ListNode* head){
	ListNode* c_head = NULL;
	while(head){
	ListNode* next = head->next;
	head->next = c_head;
	c_head = head;
	head = next;
	}
	return c_head;
	}

	ListNode* reverseKGroup(ListNode* head, int k) {
	ListNode* dummy = new ListNode(0);
	dummy->next = head;
	ListNode* tail = dummy;
	ListNode* sub_head = head;
	ListNode* toNull = head;

	while(sub_head){

	int i = k-1;
	while(i>0){
	toNull = toNull->next;
	if(toNull == NULL)
	return dummy->next;
	i–;
	}
	//Save the next head
	ListNode* temp = toNull->next;
	toNull->next = NULL;
	ListNode* new_sub_head = reverse(sub_head);

	tail->next = new_sub_head;
	tail = sub_head;
	tail->next = temp;
	sub_head = temp;
	toNull = temp;

	}
	return dummy->next;

	}
	};

view raw

ReverseNodesKGroup_RSwap.cpp

hosted with ❤ by GitHub

That’s all for today… Thanks for reading….

共享此文章：

Like this:

Related

Leave a Reply Cancel reply