Skip to content

Instantly share code, notes, and snippets.

@superlayone
Last active July 10, 2019 12:53
Show Gist options
  • Save superlayone/9916030 to your computer and use it in GitHub Desktop.
Save superlayone/9916030 to your computer and use it in GitHub Desktop.
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
Copy link

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

@Sylvia23
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
Copy link

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