链表的反转问题(Reverse Linked List)

时间:2022-08-09 19:42:44

反转单链表思路有三种,

1.将1->2->3变为 2->1->3再变为3->2->1(头插法)

2.将1->2->3变成1<-2->3再变为1<-2-<3(反转法)

3.递归

下面我们分别进行如下编码

1.头插法

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head == NULL || head->next == NULL) return head;
ListNode prehead(-1);
prehead.next = head;
ListNode *pre = &prehead;
ListNode *cur = head;

while(cur&&cur->next) {
ListNode *tmp = pre->next;
pre->next = cur->next;
cur->next = cur->next->next;
pre->next->next = tmp;
}
return prehead.next;
}
};


2.反转法

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *pre = NULL;
while(head){
ListNode* tmp = head->next;
head->next = pre;
pre = head;
head = tmp;
}
return pre;
}
};

3.递归法

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(!head || !head->next) return head;
ListNode* node = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return node;
}
};

有了最基本的链表反转操作,我们可以解决一些有意思的问题

比如判断链表是否有回文

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
if(head == NULL || head->next == NULL) return true;
ListNode* slow = head;
ListNode* fast = head;
ListNode* p = head;

while(fast->next != NULL && fast->next->next !=NULL) {
slow = slow->next;
fast = fast->next->next;
}
slow->next = reverseList(slow->next);
slow = slow->next;
while(slow){
if(head->val != slow->val)
return false;
head = head->next;
slow = slow->next;
}
return true;
}

ListNode* reverseList(ListNode* head){
ListNode* pre =NULL;
ListNode* next = NULL;
while(head != NULL) {
next = head->next;
head->next = pre;
pre = head;
head = next;
}
return pre;
}
};