Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Reverse a linked list from position m to n in-place and in one-pass.

##Leetcode-Reverse Linked List II##

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example: Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note: Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.

Analysis

  --------->1------>2------->3------->4-------5------->nullptr
  ^         ^       ^       ^         ^       ^
  |         |       |       |         |       |
  |         |       |       |         |       |
  |         |       |       |         |       |
HeadPrev  head  constPrev  prev      cur  cur->next

假设目前的m是3,n是5,那么prev-next指向cur->next,cur指向
constPrev->next,constPrev->next指向cur,然后更新cur至prev->next
思想是头插法交换node

  --------->1------>2------->4------->3-------5------->nullptr
  ^         ^       ^       ^         ^       ^
  |         |       |       |         |       |
  |         |       |       |         |       |
  |         |       |       |         |       |
HeadPrev  head  constPrev        	prev  	 cur
最后返回HeadPrev的next节点即可

Code

	/**
	 * Definition for singly-linked list.
	 * struct ListNode {
	 *     int val;
	 *     ListNode *next;
	 *     ListNode(int x) : val(x), next(NULL) {}
	 * };
	 */
	class Solution {
	public:
	    ListNode *reverseBetween(ListNode *head, int m, int n) {
	        ListNode* newHead = new ListNode(-1);
	        newHead->next = head;
	        ListNode* prev = newHead;
	        for(auto i = 0 ; i < m-1 ; i++){
	            prev = prev->next;
	        }
	        ListNode* const reversedPrev = prev;
	        //position m
	        prev = prev->next;
	        ListNode* cur = prev->next;
	        for(auto i = m ; i < n ; i++){
	            prev->next = cur->next;
	            cur->next = reversedPrev->next;
	            reversedPrev->next = cur;
	            cur = prev->next;
	        }
	        return newHead->next;
	    }
	};
@sukriti-sharma

This comment has been minimized.

Copy link

sukriti-sharma commented Sep 15, 2017

ListNode* newHead = new ListNode(-1);
Can you explain this line?

@Sylvia23

This comment has been minimized.

Copy link

Sylvia23 commented Jul 3, 2018

It means you are defining a new node whose initial value is -1. ListNode(int x) : val(x), next(NULL) {} is the constructor.

@RishabhBajaj97

This comment has been minimized.

Copy link

RishabhBajaj97 commented Feb 25, 2019

Could you please explain your approach for the above logic? A dry run did help me understand it but how did you exactly come up with this way to rearrange the links?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.