面试算法心得——反转链表

大家好，我是晴天学长，没想到，这么快就到了我比较熟悉的算法了，就是一些基本对象思维的链表，加油。💪💪💪

---

2) .算法思路

• 用三个节点挨个遍历，把整个链表给反过来。

---

3）.算法步骤

• 创建名为 reverseList 的方法，它接受一个参数 head，即链表的头节点。
• 检查 head 是否为 null。如果是，直接返回 head，因为没有需要反转的内容。
• 创建两个指针：First 和 node。将 First 初始化为 null，将 node 初始化为 head。
• 进入一个循环，只要 node 不为 null，就继续执行。
  在循环内部，创建一个新节点 next，并将其赋值为 node.next。这样做是
• 为了临时存储原始链表中的下一个节点。
• 将 node.next 更新为指向 First 节点。这实际上反转了当前节点的链接。
• 将 First 节点更新为 node 节点，因为它将成为反转后链表的新头节点。
• 通过将 node 的值设置为 next，将 node 移动到下一个节点。
• 循环结束后，原始链表中的所有节点都被反转了。
• 返回 First 节点，它是反转后链表的新头节点。

---

4）. 代码实例

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {if(head==null){return head;}ListNode First=null;ListNode node = head;while(node!=null){ListNode next = node.next;node.next=First;First= node;node=next;}return First;}
}

---

5）. 总结

• 注意，每个链表最后一个节点就是null，所以头节点应该是null

---

试题链接：