反转链表

leetcode.206

题意：反转一个单链表。

示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

经典的双指针操作链表，模拟一下然后想清楚逻辑即可，关键是要用变量tmp记录一下next。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while (cur != nullptr) {
            ListNode* tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};

类题：leetcode.19

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾，slow自然指向要删除的节点。删掉slow所指向的节点就可以了。

类题的类题：leetcode.160

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

​​

思路上，想象把两个链表的尾巴对齐，然后把长的链表的head移到短的那一个链表的开头，这样对齐以后一起向后遍历就可以了，找到地址相同就返回，如果循环结束就直接返回null就行。

​​

#include <cstdlib>
class Solution {
public:
  ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    int lenA = 0, lenB = 0;
    ListNode *nowA = headA;
    ListNode *nowB = headB;
    while (nowA) {
      lenA++;
      nowA = nowA->next;
    }
    while (nowB) {
      lenB++;
      nowB = nowB->next;
    }
    nowA = headA;
    nowB = headB;
    int jd = abs(lenA - lenB);
    if (lenA > lenB) {
      for (int i = 0; i < jd; i++) {
        nowA = nowA->next;
      }
    } else {
      for (int i = 0; i < jd; i++) {
        nowB = nowB->next;
      }
    }
    while (nowA!=nullptr) {
        if (nowA == nowB) {
            return nowA;
        }
        nowA = nowA->next;
        nowB = nowB->next;
    }
    return nullptr;
  }
};

‍