Home > Java > javaTutorial > Commonly used operations on linked lists - detailed explanation of reversal

Commonly used operations on linked lists - detailed explanation of reversal

零下一度
Release: 2017-07-19 13:40:50
Original
2063 people have browsed it

Commonly used operations on linked lists - reversal

Let’s first define a node class for a singly linked list

public class ListNode {2         
int val;3         ListNode next = null;// 指向的下个节点4 5         
ListNode(int val) {6             this.val = val;7         }8     
}
Copy after login

Implement the reversal of a singly linked list There are two methods

1. Use recursion and reverse from back to front. Start from the head node, search backward until you find the tail node, and then start reversing.​

 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     
 }
Copy after login

2. Use traversal and reverse from front to back. First save the next node, then point the current node to the previous node, and then move the node downwards to continue the cycle for the next reversal.

 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     
 }
Copy after login

As soon as I finished the online programming, I recorded it for easy reference in the future.

The above is the detailed content of Commonly used operations on linked lists - detailed explanation of reversal. For more information, please follow other related articles on the PHP Chinese website!

Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template