LeetCode206

Reverse a singly linked list.

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

Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?

206.png

這里我使用的是類似與鏈表的頭插法

#include <iostream>
#include <cstdio>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
        /*迭代法*/
    ListNode *createList()
    {
        ListNode *pHead = NULL;
        ListNode *p = pHead;
        char x;
        while(cin>>x)
        {
            if(x == 'q')
            {
                break;
            }
            
            int value = x - '0';
            ListNode *pNew = new ListNode(value);
            pNew->next = NULL;
            
            if(pHead == NULL)
            {
                pHead = pNew;
            }
            else
            {
                p->next = pNew;
            }
            p = pNew;

        }
        
        return pHead;
    }
    
    void displayList(ListNode *head)
    {

        ListNode *p = head;
        while(p != NULL)
        {
            cout<<p->val<<"->";
            p = p->next;
        }
        cout<<"NULL"<<endl;
    }
    
    ListNode* reverseList(ListNode* head) {
        ListNode *rhead = NULL;
        ListNode *p = rhead;
        ListNode *q = head;
        
        while(q != NULL)
        {
            int value = q->val;
            ListNode *pNew = new ListNode(value);
            pNew->next = NULL;
            
            if(rhead == NULL)
            {
                rhead = pNew;
            }
            else
            {
                pNew->next = rhead;
                rhead = pNew;
            }
            q = q->next;
        }
        
        return rhead;
    }
    
    /*遞歸法*/
    ListNode* reverseList2(ListNode* head) {
        if(head == NULL || head->next == NULL)
            return head;
        ListNode *p = reverseList2(head->next);
        head->next->next = head;
        head->next = NULL;
        
        return p;
    }
};


int main()
{
    Solution s;
    ListNode *head,*reverse; 
    head = s.createList();
    s.displayList(head);
    reverse = s.reverseList(head);
    s.displayList(reverse);
    
    return 0;
}

LeetCode92

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

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

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

92.png

鏈表反轉(zhuǎn)示意圖

方法一關(guān)鍵代碼：
第一步
prev->next = curr->next
第二步
curr->next = head2->next
第三步
head2->next = curr
第四步
curr = prev->next

initial.png

第一次循環(huán)1.png

第一次循環(huán)2.png

第一次循環(huán)3.png

第一次循環(huán)4.png

第一次循環(huán)結(jié)束調(diào)整.png

第二次循環(huán)1.png


第二次循環(huán)4.png

第二次循環(huán)結(jié)束.png

ListNode* reverseBetween(ListNode* head, int m, int n)
    {
        if (head == NULL) {
            return NULL;
        }
        
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        
        ListNode *iter = dummy;
        
        for (int i = 0; i < m - 1; i++) {
            iter = iter->next;
        }
        
        ListNode *prev = iter->next;
        ListNode *curr = prev->next;
        
        for (int i = 0; i < n - m; i++) {
            prev->next = curr->next;
            curr->next = iter->next;
            iter->next = curr;
            curr = prev->next;
        }
        
        return dummy->next;
    }

方法二關(guān)鍵代碼：
(沒什么關(guān)鍵代碼)就是非常直觀的思路
取出鏈表中需要反轉(zhuǎn)的部分，單獨反轉(zhuǎn)，然后在和別的正常部分接在一起。
需要注意的就是鏈表只有一個數(shù)時的反轉(zhuǎn)。

果然自己頭腦太簡單，只能用巨多的if-else來補充了。。

雖然兩種方法提交都沒什么差別

測試用例

1->2->3->4->5 , m=2, n=4

5 , m=1, n=1

ListNode* reverseBetween(ListNode* head, int m, int n)
    {
        int length = 0;
        ListNode *point = head;
        ListNode *L1 = NULL;
        ListNode *L2 = NULL;
        ListNode *L3 = NULL;
        
        ListNode *reverse_b;
        
        ListNode *p,*q,*r;
        p = L1;
        q = L2;
        r = L3;
        
        while (point != NULL)
        {
            int value = point->val;
            ListNode *New = new ListNode(value);
            New->next = NULL;
            length ++;
            
            if(length>0 && length<m)
            {
                if(L1 == NULL)
                {
                    L1 = New;
                }
                else
                {
                    p->next = New;
                }
                p = New;
            }
            else if (length>=m && length<=n)
            {
                if(L2 == NULL)
                {
                    L2 = New;
                    q = New;
                }
                else
                {
                    New->next = L2;
                    L2 = New;
                }
            }
            else
            {
                if(L3 == NULL)
                {
                    L3 = New;
                }
                else
                {
                    r->next = New;
                }
                r = New;
            }
            
            point = point->next;
        }

        if(L1 == NULL)
        {
            if(L2 == NULL)
            {
                if(L3 == NULL)
                {
                    reverse_b = reverse_b;
                }
                else
                {
                    reverse_b = L3;
                }
            }
            else // L2!=NULL
            {
                if(L3 == NULL)
                {
                    reverse_b = L2;
                }
                else //L3!=NULL
                {
                    reverse_b = L2;
                    q->next = L3;
                }
            } 
        }
        else //L1!=NULL
        {
            if(L2 == NULL)
            {
                if(L3 == NULL)
                {
                    reverse_b = L1;
                }
                else //L3!=NULL
                {
                    reverse_b = L1;
                    p->next = L3;
                }
            }
            else // L2!=NULL
            {
                if(L3 == NULL)
                {
                    reverse_b = L1;
                    p->next = L2;
                }
                else //L3!=NULL
                {
                    reverse_b = L1;
                    p->next = L2;
                    q->next = L3;
                    
                }
            } 
        }
        
        return reverse_b;
    }