LeetCode中链表转置问题总结

链表转置是很常见的一类链表题目，最近在刷LeetCode题目时，发现链表转置还有这么多的变形，在这里对LeetCode中链表转置的题目进行一下总结。

转置整个链表

Reverse a singly linked list.

Example:

1 2	Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL

这道题是链表转置最一般的情况了，需要转置整个单链表。最常见的迭代解法是设置一个prev指针，依次将每个结点的next指针指向prev，遍历的过程中需要提取保存next指针，prev指针也不断向后变化，最后返回prev，代码如下：

public ListNode reverseList(ListNode head) {
	ListNode prev = null;
    while(head != null) {
        ListNode next = head.next;
        head.next = prev;
        prev = head;
        head = next;
     }
     return prev;
 }

最后返回的prev指针指向的是转置后链表的头结点。当然，这题也可以用递归解法来做，这里不再具体阐述。

转置区间链表

LeetCode 92

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

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

1 2	Input: 1->2->3->4->5->NULL, m = 2, n = 4 Output: 1->4->3->2->5->NULL

这道题和上道题有些差别，可以说上道题是这道题的特殊情况，只不过把m=1，n=链表的长度，从这道题我们将总结链表转置的一般性解法。这道题转置区间链表需要保存开始反转位置的前一个结点（即m-1），反转的最后一个结点n，以及其下一个结点n+1。因为在反转结束后，需要将m-1的next指针指向反转后的头结点，将反转后的尾结点的next指向n+1。

方法一

如果使用上道题的解法，需要稍微变换一下，增加一个结束结点参数，相应代码如下：

private ListNode reverse(ListNode start, ListNode end) {
     ListNode prev = end;
     while(start != end) {
         ListNode next = start.next;
         start.next = prev;
         prev = start;
         start = next;
     }
     return prev;
 }

上述start为开始反转的结点，end为反转结束结点的下一个结点。上述函数返回的是反转后的头结点，还需要获得其尾结点，其实仔细观察就可以发现传入的start参数(即反转开始结点)在转置后就指向了反转后的尾结点。这道题的代码如下：

public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null || m == n) {
        	return head;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode end = dummy.next;
        for (int i=0; i<n; i++) {
        	if (i < m-1) {
        		pre = pre.next;		//find m-1 node	
        	}
        	end = end.next;
        }
  
        ListNode start = pre.next;
        ListNode revHead = reverse(start, end);
        pre.next = revHead;
        start.next = end;	//start为转置后的尾结点，将其指向下一个结点
        return dummy.next;
    }

方法二

针对这道题，链表转置还有另一种方法，首先设置一个虚拟结点指向head（因为可能要改变头结点），对要转置的每一个结点，依次遍历将其放到最前面。相应代码如下：

private ListNode reverse(ListNode pre, ListNode next) {
   ListNode last = pre.next;
   ListNode cur = last.next;
   while(cur != next) {
   	last.next = cur.next;
   	cur.next = pre.next;
   	pre.next = cur;
   	cur = last.next;
  	}
  	return last;
}

prev为要转置的结点的前一个结点，next指向转置区间最后一个结点的下一个结点。每次将结点放到前面（将prev指针指向该结点），最终返回的结点指向的是转置后的最后一个结点，这样就不需要找最后一个结点了。使用该方法代码如下：

public ListNode reverseBetween(ListNode head, int m, int n) {
       if (head == null || m == n) {
       	return head;
       }

       ListNode dummy = new ListNode(0);
       dummy.next = head;
       ListNode pre = dummy;
       ListNode end = dummy.next;
       for (int i=0; i<n; i++) {
       	if (i < m-1) {
       		pre = pre.next;		//find m-1 node	
       	}
       	end = end.next;
       }

       ListNode last = reverse(pre, end);
       last.next = end;
       
       return dummy.next;
   }

上述代码在转置的过程中就已经将pre指向链表的头结点了，只需要将返回的last指向下一个结点就行了。

分组转置链表

LeetCode 25

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.

这道题应该是链表转置中比较难的了，要求每k个元素进行转置，其实也是上面区间转置的变形，只不过这个区间长度固定为k，并且有多个区间。这道题可以借用上道题的第二种方法，首先设置虚拟节点指向head，找到下一个分组的最后一个节点的next，每次转置后返回的是这一分组的最后一个节点（即下一个分组的前一个节点），相应代码如下：

public ListNode reverseKGroup(ListNode head, int k) {
    if (head == null || k == 1) {
    	return head;
    }

    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode pre = dummy;
    int i = 0;
    while(head != null) {
    	i++;
    	if (i % k == 0) {
    		pre = reverse(pre, head.next);
    		head = pre.next;
    	} else {
    		head = head.next;
    	}
    }
    return dummy.next;
}

private ListNode reverse(ListNode pre, ListNode next) {
	ListNode last = pre.next;
	ListNode cur = last.next;
	while(cur != next) {
		last.next = cur.next;
		cur.next = pre.next;
		pre.next = cur;
		cur = last.next;
	}
	return last;
}

* an example:
* a linked list:
* 0->1->2->3->4->5->6
* |           |   
* pre        next
* after call pre = reverse(pre, next)
* 
* 0->3->2->1->4->5->6
*          |  |
*          pre next

总结与感想

（1）链表涉及到头结点改变的，往往需要新建一个dummy结点指向原来的头结点，这样就算头结点变动了，我们还可以通过dummy->next来获得新链表的头结点。

（2）对链表问题要多在纸上画图，模拟过程，用不同的方法，总结这些方法的共性。

参考资料：

http://www.cnblogs.com/grandyang/p/4306611.html

https://www.cnblogs.com/lichen782/p/leetcode_Reverse_Nodes_in_kGroup.html