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

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

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

试题链接：