206. Reverse Linked List&&92. Reverse Linked List II

题目

Reverse a singly linked list.

大意

反转链表

答案

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL || head->next == NULL) {
            return head;
        }    
        ListNode* prev=NULL;
        ListNode* cur=head;
        while(cur != NULL) {
            ListNode* temp = cur->next;//cur 存在 cur->next 一定存在.
            cur->next = prev;
            prev = cur;
            cur = temp;   
        }
        return prev;
    }
};

思路

经典算法题,但是写了好久,之前设置了一个头节点,反转的时候没有去掉,结果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) 
    {
        ListNode* tou =new ListNode(-1);
        tou->next = head;
        ListNode* pre =tou;
        if(n<=m) return head;
        int t =n-m;
        while(m>1)
        {
            pre=pre->next;
            m--;
        }
        ListNode* p = pre->next; //p是第m个节点.
        for(int i=0;i<t;i++)
        {
            ListNode* post = p->next;
            p->next =post->next;
            post->next =pre->next;
            pre->next=post;
        }
        return tou->next;
    }
};

思路

设置头节点,找到最前面的更新节点.