LeetCode206 实现单链表的反转

LeetCode 码，码不停题

1.题目介绍

Reverse a singly linked list.

Example:

Input:1->2->3->4->5->NULL

Output:5->4->3->2->1->NULL

2.实现方式

就地反转法

新建链表，头节点插入法

递归反转法

3.代码实现

不啰嗦，直接看代码实现，本文代码主要采用java编写

单链表实现欢迎参考文章https://blog.csdn.net/u014229347/article/details/88966409)

/**
 * 实现单链表的反转(LeetCode206)
 *
 * @author llspace
 * @since 2019-06-28
 */
public class SingleLinkedListReverse {
 public static void main(String[] args) {
 SingleLinkedList<Integer> singleLinkedList = new SingleLinkedList<>();
 singleLinkedList.addHead(1);
 for(int i = 2; i < 6; i++){
 singleLinkedList.addNode(i, i-1);
 }
 singleLinkedList.print();
 //测试单链表反转
 //singleLinkedList = reverse(singleLinkedList);
 //singleLinkedList = reverse1(singleLinkedList);
 singleLinkedList = reverse2(singleLinkedList);
 singleLinkedList.print();
 }
 /**
 * 就地反转法
 *
 * @param input
 * @return
 */
 public static SingleLinkedList<Integer> reverse(SingleLinkedList<Integer> input){
 SingleLinkedList.Node<Integer> head = input.getHead();
 SingleLinkedList.Node<Integer> next = head.next;
 while(next != null){
 input.addHead(next.value);
 head.next = next.next;
 next = next.next;
 }
 return input;
 }
 /**
 * 新建链表，头节点插入法
 *
 * @param input
 * @return
 */
 public static SingleLinkedList<Integer> reverse1(SingleLinkedList<Integer> input){
 SingleLinkedList<Integer> output = new SingleLinkedList<>();
 SingleLinkedList.Node<Integer> head = input.getHead();
 while(head != null){
 output.addHead(head.value);
 head = head.next;
 }
 return output;
 }
 /**
 * 递归反转法
 *
 * @param input
 * @return
 */
 public static SingleLinkedList<Integer> reverse2(SingleLinkedList<Integer> input){
 input.setHead(reverseNode(input.getHead()));
 return input;
 }
 public static SingleLinkedList.Node<Integer> reverseNode(SingleLinkedList.Node<Integer> head){
 if(head == null || head.next == null) {
 return head;
 }
 SingleLinkedList.Node<Integer> node = reverseNode(head.next);
 head.next.next = head;
 head.next = null;
 return node;
 }
}

好了今天就码到这了，欢迎感兴趣的朋友们一起交流！