Reverse Linked List II

文章目录

1. Reverse Linked List II

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.

思路

其实跟反转链表的思路是一样的，都采用头插法，只不过这里的头需要重新定义，还有插入次数的的限定n-m。

解题

c++版

/**
 * 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) {
        int i;
        ListNode dummy(-1);
        dummy.next=head;
        ListNode *dummy1=&dummy;
        for(i=1;i<m;i++){
            dummy1=dummy1->next;
        }
        ListNode *pre,*cur;
        pre=dummy1->next;
        cur=pre->next;
        for(i=0;i<n-m;i++){
            pre->next=cur->next;
            cur->next=dummy1->next;
            dummy1->next=cur;
            cur=pre->next;
        }
        return dummy.next;
    }
};

Python版

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param head, a ListNode
    # @param m, an integer
    # @param n, an integer
    # @return a ListNode
    def reverseBetween(self, head, m, n):
        dummy=ListNode(-1)
        dummy.next=head
        prev=dummy
        for i in range(m-1):
            prev=prev.next
        head2=prev
        prev=head2.next
        cur=prev.next
        for i in range(n-m):
            prev.next=cur.next
            cur.next=head2.next
            head2.next=cur
            cur=prev.next
        return dummy.next