Reverse Linked List II

原题: https://leetcode.com/problems/reverse-linked-list-ii/description/

题意: 将链表的[m,n]段就地逆置,一趟遍历完成。

约定:(1)1 ≤ m ≤ n ≤ 链表的长度。

例子: 

给定:链表=1->2->3->4->5->NULL,m = 2, n = 4
返回:1->4->3->2->5->NULL
标签: linked、reverse、链表、ii、地逆置、面试
猜你感兴趣的圈子:
LeetCode交流圈
  • Bingo
    2017-08-12 09:30:12 1楼#1层
    Python:
    class Solution:
        # @param head, a ListNode
        # @param m, an integer
        # @param n, an integer
        # @return a ListNode
        def reverseBetween(self, head, m, n):
            dummyNode = ListNode(0)
            p = dummyNode
            q = head
    
            for x in range(m - 1):
                p.next = q
                q = q.next
                p = p.next
    
            start = None
            end = q
            next = None
            for x in range(m, n + 1):
                next = q.next
                q.next = start
                start = q
                q = next
    
            p.next = start
            end.next = next
            return dummyNode.next
  • Bingo
    2017-08-12 09:32:27 2楼#1层
    Java:
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {  
        // Divide the list to three parts:   
        // 1)Nodes before m keep still;   
        // 2)Traverse m~n nodes;  
        // 3)Nodes after n keep still.  
        public ListNode reverseBetween(ListNode head, int m, int n) {  
            if (m == n) return head;  
              
            ListNode preHead = new ListNode(0);  
            preHead.next = head;  
              
            // The (m-1) node is the tail of first tail.  
            ListNode firstTail = preHead;  
            int k = m - 1;  
            while (k-- > 0) {  
                firstTail = firstTail.next;  
            }  
              
            // The m-th node is the traversed tail.  
            ListNode secondTail = firstTail.next;  
              
            // Traverse m~n nodes, and get the traversed head.  
            ListNode tmpHead = null;  
            ListNode tmpNext = null;  
            ListNode node = firstTail.next;  
            k = n - m + 1;  
            while (k-- > 0) {  
                tmpHead = node;  
                node = node.next;  
                  
                tmpHead.next = tmpNext;  
                tmpNext = tmpHead;  
            }  
              
            // Connect three parts.  
            firstTail.next = tmpHead;  
            secondTail.next = node;  
              
            return preHead.next;  
        }  
    }
  • Bingo
    2017-08-12 09:33:17 3楼#1层
    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) {
            ListNode *dummy = new ListNode(-1);
            dummy->next = head;
            ListNode *cur = dummy;
            ListNode *pre, *front, *last;
            for (int i = 1; i <= m - 1; ++i) cur = cur->next;
            pre = cur;
            last = cur->next;
            for (int i = m; i <= n; ++i) {
                cur = pre->next;
                pre->next = cur->next;
                cur->next = front;
                front = cur;
            }
            cur = pre->next;
            pre->next = front;
            last->next = cur;
            return dummy->next;
        }
    };
  • 回复
隐藏