面试高频题-反转链表

最近开始分享一些面试的高频题，方向有算法，数据结构，unity，c#，c++，渲染图形学等

我准备做成一个合集，内容适合小白，讲解详细生动，真正让大家搞懂一些问题

好了，闲话少说，我们开始第一篇算法

为什么是算法呢，很多老鸟可能嗤之以鼻，其实高端面试首面必是算法和数据结构，如果你答得不好，那基本不会有第二面

为什么如此简单粗暴的残酷?

1. 1.因为在所有的面试中，只有算法和数据结构是没法背的，是没法伪装的，你会就是会，不会就是不会，项目经历和八股文都是可以伪装的
   
   
2. 2.你代码写的怎么样，时间复杂度，空间复杂度等，看你是不是聪不聪明，靠算法是最容易看出来的
   
   
3. 3.你的思维的严谨性，对于边界，极值是否有考虑，你的程序是否健壮
   
   

如果你还想进一线大厂，或者国际大厂，请重视算法，你如果就这么混混请忽略下面的内容

下面我们开始今天的面试题吧

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

输入：head = [1,2,3,4,5]

输出：[5,4,3,2,1]

输入：head = [1,2]

输出：[2,1]

好了，现在开始你不要百度，不要google，不要chatgpt

尽量自己独立思考去解决这道题，而不是看答案

哪怕你想出来最差的解法，

那也是你自己的如果你看了答案，

对不起，你下次做次做，我保证你还是不会这样你第一次做完全是浪费时间

---独立思考分割线-----------------------------------------------

这道题，你如果用栈什么的，时间复杂度会O(n)

其实你要答到双指针迭代法，具体为啥可以看下面的视频

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode ReverseList(ListNode head) {
           ListNode pre = null;
           ListNode cur = head;
           while(cur != null){
               ListNode tmp = cur.next; //为防止指针断开，先拿一个临时变量先存储cur的next节点
               cur.next = pre;   //反转链表
               pre= cur;  //pre移动到cur
               cur = tmp; //cur移动到next
           }
           return pre;
    }
}