leetcode LinkList专题

柔光的暖阳◎ 2022-08-08 05:28 151阅读 0赞

此次blog会将leetcode上的linklist专题内容放在这里，后续慢慢添加

一：leetcode 206 [Reverse Linked List][] 二：leetcode 92 [Reverse Linked List II][]

一：leetcode 206 [Reverse Linked List][]

题目：

Reverse a singly linked list.

代码：

class Solution {
    public:
        ListNode* reverseList(ListNode* head) {
            if(head == NULL) return NULL;
            ListNode *p = head;
            ListNode *pNext = p->next;
            p->next = NULL;       // 头结点需要指向NULL 否则time limit
            while(pNext != NULL){
                ListNode *q = pNext->next;
                pNext->next = p;
                p = pNext;   // 迭代
                pNext = q;
            }
            return p;
            
        }
    };

二：leetcode 92 [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.

分析：此题比一稍微复杂一点，但是也是很容易求解的

代码：

class Solution {
    public:
        ListNode* reverseBetween(ListNode* head, int m, int n) {
            if(m == n) return head;
            ListNode *pre = head;
            ListNode *p = head;
            for(int i = 1; i < m; i++){    // 找到第m个元素和其前一个元素
                pre = p;
                p = p->next;
            }
            ListNode *curr = p;
            ListNode *pNext = p->next;   // 对中间需要进行reverse的元素进行反转 利用reverse linked list中的思想
            for(int i = m; i < n; i++){
                ListNode *q = pNext->next;
                pNext->next = p;
                p = pNext;
                pNext = q;
            }
            curr->next = pNext;
            if(pre != curr)pre->next = p;      // 不相等表明是m!=1  那么 则pre->next = p,,相等表明m==1，那么head ==p
            else head = p;
            return head;
            
        }
    };

[Reverse Linked List]: https://leetcode.com/problems/reverse-linked-list/
[Reverse Linked List II]: https://leetcode.com/problems/reverse-linked-list-ii/