LeetCode-Reverse Linked List II（反转链表）

小灰灰 2022-08-07 02:43 3阅读 0赞

题目：

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.

题目要求比较多，原地和只能遍历一次，解题思路，删除节点，一直进行插入，比如上例：

1->2->3->4->5->NULL，删除2，1->3->4->5->NULL，在1后面插入，结果如下：

1->2->3->4->5->NULL，删除3，1->2->4->5->NULL，在1后面插入，结果如下：

1->3->2->4->5->NULL，删除4，1->3->2->5->NULL，在1后面插入，结果如下：

1->4->3->2->5->NULL，即为结果，代码如下：

public ListNode reverseBetween(ListNode head, int m, int n) {
            ListNode preNode = new ListNode(0);
            preNode.next = head;
            head = preNode;
            int i = 0;
            while (i < m-1) {
            	preNode = preNode.next;
            	i++;
            }
            ListNode curNode = preNode;
            while (i < n && curNode != null) {
            	ListNode node = curNode.next;
            	curNode.next = curNode.next.next;
            	node.next = preNode.next;
            	preNode.next = node;
            	if (preNode == curNode)
            		curNode = curNode.next;
            	i++;
            }
        	return head.next;
        }

当然也可以是另外一个思路，分两个链表。比如上例：

A:1->NULL

B:2->3->4->5->NULL

将B的节点以此插入A链表1的后面，知道m-n+1节点为止！两种方法的思路差不多