📑本篇内容：链表反转与复制（简单）

📘 文章专栏：《剑指offer》 面试高频数据结构与算法

🎬最近更新：2022年1月21日 《剑指Offer》——栈与队列简单应用 如果遇到栈与队列的相关问题不妨多来个辅助栈

🙊个人简介：一只二本院校在读的大三程序猿，本着注重基础，打卡算法，分享技术作为个人的经验总结性的博文博主，虽然可能有时会犯懒，但是还是会坚持下去的，如果你很喜欢博文的话，建议看下面一行~（疯狂暗示QwQ）

🌇点赞 👍 收藏 ⭐留言 📝 一键三连 _{关爱程序猿，从你我做起}

剑指Offer——简单的链表反转与复制

🙊写在前面🙊

没想到今天咱们又在本栏见面了，今天的力扣题对于我这个小菜鸡来说太过于繁琐与复杂了，能看懂别人写的题解已经很不错了，再让我下手去写题解，确实有点为难我了，按照上期所说，如果每日一题的题目无法更新题解，就拿这个栏目来凑数了哦~感谢您的收看呀，今天咱们的题是对链表的简单应用，难度不大，包含了链表的反转与复制，是否真的有那么简单呢？看看就知道了 。

1、剑指 Offer 24. 反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例

示例1：

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

提示

0 <= 节点个数 <= 5000

📝思路📝

设置三个节点分别用来记录当前指针位置、前置指针位置、后置指针位置，简单的理解就是当前指针指向前置指针的位置，并且将所有指针后移遍历。

⭐代码实现⭐

class Solution {public ListNode reverseList(ListNode head) {//初始化前置指针为nullListNode preNode = null;//初始化当前指针所指ListNode curNode = head;//如果当前指针还有下一个元素时进入循环while (curNode!=null){//用于记录下个节点ListNode nextNode = curNode.next;//当前指针的下一个节点指向前置指针curNode.next = preNode;//当前节点变为了前置节点preNode = curNode;//下一个节点变为了当前节点curNode = nextNode;}return preNode;}
}

运行结果

---

2、剑指 Offer 06. 从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例

示例1：

输入：head = [1,3,2]
输出：[2,3,1]

提示

0 <= 链表长度 <= 10000

📝思路📝

有了上题的思路，这道题对你还有难点没有嘛~直接将链表反转，依次遍历里面的值添加到结果数组中就好了哦！！！

⭐代码实现⭐

class Solution {public int[] reversePrint(ListNode head) {//用于记录链表中的元素个数int n = 0;ListNode curNode = head;//初始化链表个数while (curNode!= null ){n++;curNode = curNode.next;}  //创建结果数组int []res = new int [n];//反转链表head = reverse(head);//把结果进行添加for (int i = 0 ;i< n;i++){res[i] = head.val;head = head.next;}return res;}//上一题的反转链表的方法public ListNode reverse(ListNode head){ListNode preNode = null;ListNode curNode = head;while (curNode != null){ListNode nextNode = curNode.next;curNode.next = preNode;preNode = curNode;curNode = nextNode;}return preNode;}
}

运行结果

3、剑指 Offer 35. 复杂链表的复制

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例

示例1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

提示

-10000 <= Node.val <= 10000
Node.random 为空（null）或指向链表中的节点。
节点数目不超过 1000 。

📝思路📝

• 在每个节点之后复制一个与其一致的节点。
  例如:
  1->2->3->null, 复制之后就是1->1->2->2->3->3->null
• 遍历整个链表，判断原链表节点是否存在random，如果存在就进行将 源节点的随机映射位置赋给 新复制出来的节点。
• 将上述的一整个链表一分为二。

⭐代码实现⭐

class Solution {public Node copyRandomList(Node head) {if (head == null) {return head;}Node curNode = head;//遍历复制节点    while(curNode != null){Node copyNode = new Node(curNode.val);copyNode.next = curNode.next;curNode.next = copyNode;curNode = curNode.next.next;}//对节点的随机节点映射进行复制curNode = head;while (curNode!=null){//判断是否存在random随机映射if (curNode.random != null){//如果存在的话 当前新复制的节点的随机映射，就是原节点随机映射的位置对应的数字的复制节点curNode.next.random = curNode.random.next;}curNode = curNode.next.next;}Node copyHead = head.next;curNode = head;Node curCopy = head.next;//将链表一分为二 拆出新复制的链表while(curNode!=null){curNode.next = curNode.next.next;curNode = curNode.next;if (curCopy.next != null){curCopy.next = curCopy.next.next;curCopy = curCopy.next;}}return copyHead;}
}

运行结果

🙊写在最后🙊

2022-1-24 今天小付打卡了哦~

美好的日出 美好的山河

都因有你存在 而璀璨 耀眼