单向链表每一个节点(node)就是一个结构体指针，包含：
- 节点元素数据；
- 当前节点的指针地址；
- 当前节点的指针地址；下一个节点的指针地址。
leetcode链表表示方法：
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};leetcode206.反转链表#
迭代法#
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;
}- 时间复杂度：O(n)
- 空间复杂度：O(1)
递归法#
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);
}- 时间复杂度：O(n)
- 空间复杂度：O(n)
return reverseList(head_next, head);
- 这是尾递归形式。 #尾递归 #递归
- 将“下一个要处理的节点” (head_next) 作为新的 head 传进去。
- 将“当前节点” (head) 作为下一次递归的 head_prev 传进去。
笔记
迭代法中，ListNode *head_prev = nullptr位于函数内部；递归法中，ListNode *head_prev = nullptr位于函数参数内
·迭代法：它只在这一次函数调用中存在，且一共只调用了一次。
·递归法：每一个递归层级（每一层函数调用）都有它自己的head_prev。
leetcode234.回文链表#
快慢指针法#
刚做完反转链表的题目，所以立刻想到的是反转后半段链表，然后比较前半段和后半段是否相同。其实把链表放到数组中再进行回文比较显然是代码量更小的方法，但快慢指针的好处也显而易见：避免使用 O(n) 额外空间。
bool isPalindrome(ListNode* head) {
if(head==nullptr||head->next==nullptr){
return true;
}
ListNode* head1=head; //head1慢指针
ListNode* head2=head; //head2快指针
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);
}