我们先来定义一个单链表的节点类
public class ListNode {2 int val;3 ListNode next = null;// 指向的下个节点4 5 ListNode(int val) {6 this.val = val;7 }8 }
实现单链表反转共有两种方法
1、使用递归,从后往前反转。从头结点开始,往后查找直到找到尾节点为止,然后开始反转。
1 public ListNode reverseList(ListNode head) { 2 if (head == null || head.next == null) 3 return head; 4 5 ListNode prev = reverseList(head.next);// 递归调用,先反转下个节点 6 7 head.next.next = head;// 将当前结点的指针域指向前一结点 8 head.next = null;// 前一结点的指针域令为null; 9 return prev;// 反转后新链表的头结点10 }
2、使用遍历,从前往后反转。先保存下个节点,然后将将当前节点指向前个节点,然后在将节点向下移动继续循环进行下次反转。
1 public ListNode reverseList(ListNode head) { 2 if (head == null) { 3 return null; 4 } 5 ListNode pre = null; 6 ListNode next = null; 7 while (head != null) { 8 // 保存下个节点,防止丢失 9 next = head.next;10 // 将他的下个节点指向前个节点11 head.next = pre;12 13 // head指向pre后,就继续依次反转下个节点14 // 让pre,head依次向后移动一个节点,继续下一次的反转15 pre = head;16 head = next;17 }18 return pre;19 }
刚做完在线编程,就随手记录下来,方便日后查看。
Atas ialah kandungan terperinci 链表常用操作——反转详解. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!