1. 单链表反转 实现
public class testLinkedList{ //单链表 节点(存储int型数据) public static class Node{ public int value; public Node next; public Node(int data){ this.value = data; } } //实现单链表反转 public static Node reverse(Node head){ private Node pre = null; private Node next = null; while(head != null){ next = head.next; head.next = pre; pre = head; head = next; } return pre; } }
2. 双链表反转 实现
public class testDoubleLinkedList{ //双链表 节点（存储int型数据） public static class DoubleNode{ public int value; public DoubleNode last; public DoubleNode next; public DoubleNode(int data){ this.value = data; } } //双链表反转 实现 public static DoubleNode reverse(DoubleNode head){ public DoubleNode next = null; public DoubleNode pre = null; while(head != null){ next = head.next; head.next = pre; head.last = next; pre = head; head = next; } return pre; } }
3. 相关题型
① 剑指 Offer II 024. 反转链表 - 力扣（LeetCode）
题目：
给定单链表的头节点
head，请反转链表，并返回反转后的链表的头节点。示例 1 :
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
示例 2 ：
输入：head = [1,2] 输出：[2,1]
示例 3 :
输入：head = [] 输出：[]
解答：
/** * 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) { ListNode next = null; ListNode pre = null; while(head != null){ next = head.next; head.next = pre; pre = head; head = next; } return pre; } }
AC：
② 92. 反转链表 II - 力扣（LeetCode）
题目:
给你单链表的头指针
head和两个整数left和right，其中left <= right。请你反转从位置left到位置right的链表节点，返回 反转后的链表 。示例 1：
输入：head = [1,2,3,4,5], left = 2, right = 4 输出：[1,4,3,2,5]
示例 2：
输入：head = [5], left = 1, right = 1 输出：[5]
提示 :
- 链表中节点数目为
n1 <= n <= 500-500 <= Node.val <= 5001 <= left <= right <= n
解答：
- 先遍历，获取到left位置节点与right位置节点
- 遍历过程中，还需获取left位置前一个节点和right位置后一个节点
- 之后，将left到right范围内的链表反转
- 最后维护好反转后链表的头部与尾部指针，并返回头节点即可。
/** * 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 reverseBetween(ListNode head, int left, int right) { //left 与 right 在同一个位置，无须交换。 if(left == right) return head; ListNode next = null; //当前节点的后一个节点 ListNode pre = null; //当前节点的前一个节点 ListNode leftPre = null; //left位置节点的前一个节点 ListNode rightNext = null; //right位置节点的后一个节点 ListNode Left = null; //left位置节点 ListNode Right = null; //right位置节点 ListNode curr = head; //当前节点指向head节点 boolean flag = false; //记录left位置是否为head节点 if(left == 1){ //left在第一个位置，说明left位置是head节点 flag = true; Left = curr; } for(int i = 1;i <= right;++i){ if((i + 1) == left){ leftPre = curr; Left = curr.next; } if(i == right){ Right = curr; rightNext = curr.next; } curr = curr.next; } //将left到right位置的链表反转 curr = Left; while(curr != rightNext){ next = curr.next; curr.next = pre; pre = curr; curr = next; } //反转后，left的下一个指向原本right的下一个 Left.next = rightNext; if(flag){ //若在一开始left就是head return Right; //反转完原本right位置的节点就是头节点 } //若在一开始left在head后面，还需要将原本left前一个作为原本right前一个 leftPre.next = Right; return head; } }
AC:
