Each node in a singly linked list is a struct pointer, which contains:
- Node element data;
- The pointer address of the next node.
LeetCode linked list representation:
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};leetcode206. Reverse Linked List#
Iterative Method#
ListNode* reverseList(ListNode* head) {
ListNode *head_prev = nullptr, *head_next;
while (head) {
head_next = head->next;
head->next = head_prev;
head_prev = head;
head = head_next;
}
return head_prev;
}- Time Complexity: O(n)
- Space Complexity: O(1)
Recursive Method#
ListNode* reverseList(ListNode* head, ListNode* head_prev = nullptr) {
if (head == nullptr) {
return head_prev;
}
ListNode* head_next = head->next;
head->next = head_prev;
return reverseList(head_next, head);
}- Time Complexity: O(n)
- Space Complexity: O(n)
return reverseList(head_next, head);
- This is in tail recursion form. #TailRecursion #Recursion
- Pass the “next node to process” (head_next) as the new
head. - Pass the “current node” (head) as the
head_prevfor the next recursion loop.
In the iterative method, ListNode *head_prev = nullptr is located inside the function; in the recursive method, ListNode *head_prev = nullptr is within the function parameters.
· Iterative: It only exists in this single function call, which is executed only once.
· Recursive: Each recursion level (each function call) has its own head_prev.
leetcode234. Palindrome Linked List#
Fast and Slow Pointers#
Having just finished the problem on reversing a linked list, I immediately thought of reversing the second half of the list and then comparing whether the first and second halves are identical. While putting the linked list into an array for palindrome comparison would clearly involve less code, the advantage of fast and slow pointers is obvious: it avoids using O(n) extra space.
bool isPalindrome(ListNode* head) {
if(head==nullptr||head->next==nullptr){
return true;
}
ListNode* head1=head; // head1 slow pointer
ListNode* head2=head; // head2 fast pointer
while(head2!=nullptr&&head2->next!=nullptr){
head1=head1->next;
head2=head2->next->next;
}
ListNode* secondHalf=reverseList(head1,nullptr);
ListNode* p1=head;
ListNode* p2=secondHalf;
bool flag=true;
while(p2!=nullptr){
if(p1->val!=p2->val){
flag=false;
break;
}
p1=p1->next;
p2=p2->next;
}
return flag;
}
ListNode* reverseList(ListNode* head,ListNode *head_prev = nullptr) {
ListNode *head_next;
if(head==nullptr){
return head_prev;
}
head_next=head->next;
head->next=head_prev;
return reverseList(head_next,head);
}