PhyCmdBlock的做题笔记

外观

206. 反转链表 ​

力扣题目链接

头插法 ​

这个是我看了课内数据结构以后写的。那里说，头插法可以用于反转链表，于是我就搞了一个头插法：

cpp
class Solution {
  public:
	ListNode *reverseList(ListNode *head)
	{
		ListNode *new_list = nullptr;
		ListNode *p = head;
		while (p != nullptr) {
			ListNode *s = new ListNode;
			s->val = p->val;
			s->next = new_list;
			new_list = s;
			p = p->next;
		}
		return new_list;
	}
};

做法是正确的，也通过了。但是我看答案知道，标准做法不是按照数据结构那里面写的，而是直接原地反转指针方向，实现存储空间O(1).

就是新建了一个链表，new_list是新链表的头指针。由于这个题目的设计里是没有头结点的，所以这个头指针初值是null。p用来遍历旧链表，然后开始遍历，每个结点都会让新链表创建一个结点，旧值赋过去，新的next变成头结点，这样才能实现一直在头部插入。

原地反转 ​

双指针写法 ​

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

普遍的标准写法，不占用新空间，更优。就是从头开始依次遍历，只修改next指针，不动数据域。记录两个指针，pre代表旧链表中cur前面那个结点，将会被结点用作next，也就代表了新链表中cur后面的结点；cur是当前修改的结点。cur初始指向第一个结点，pre的初值作为第一个结点前面的结点，或者说在新链表中最后一个结点指向的位置，是一个null。然后开始遍历。先保存一下cur的位置，防止cur往下走的时候把当前位置信息丢失。然后cur往下走。接下来处理tmp也就是原cur的next，next指向pre，这样指向的方向就反过来了。然后更新pre，因为cur已经往下走了，所以pre已经变成了原cur，即tmp。

递归写法 ​

TODO