链表的操作-反转链表

链表

160相交链表

代码

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* h1=headA;ListNode* h2=headB;while(h1&&h2){if(h1!=h2){h1=h1->next;h2=h2->next;}else{return h1;}}if(h1==nullptr){h1=headB;}else{h2=headA;}while(h1&&h2){if(h1!=h2){h1=h1->next;h2=h2->next;}else{return h1;}}if(h1==nullptr){h1=headB;}else{h2=headA;}while(h1&&h2){if(h1!=h2){h1=h1->next;h2=h2->next;}else{return h1;}}return nullptr;}
};

代码优化

通过两次遍历，headA，headB走的距离一定是一样的。
最终只会出现两种情况：

1. 相等指向同一个ListNode，
2. 两个链表中没有相交的点，又因为最后指向的都是空指针

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* h1=headA;ListNode* h2=headB;while(h1!=h2){h1=(h1==nullptr)?headB:h1->next;h2=(h2==nullptr)?headA:h2->next;}return h1;}

其他方法

1. 记录长度，这个办法好像没办法解决，因为你不知道长度在那？
2. 通过map，set存放ListNode，然后边遍历，边计算是否存在

反转链表

1. 方法1：

    ListNode* reverseList(ListNode* head) {ListNode* pre=nullptr;ListNode* cur=head;while(cur){ListNode* ne=cur->next;cur->next=pre;pre=cur;cur=ne;}return pre;}

方法2：

 ListNode* reverseList(ListNode* head) {ListNode* pre=new ListNode(-1);ListNode* cur=head;while(cur){ListNode* ne=cur->next;cur->next=pre->next;pre->next=cur;cur=ne;}ListNode* t=pre->next;delete pre;return t;}

递归的方法

ListNode* reverseList(ListNode* head) {if(head==nullptr||head->next==nullptr){return head;}ListNode* last=reverseList(head->next);head->next->next=head;head->next=nullptr;return last;}
e* last=reverseList(head->next);head->next->next=head;head->next=nullptr;return last;}