Advertisement
DulcetAirman

reverse singly linked list

May 5th, 2018
150
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package ch.claude_martin;
  2.  
  3. import java.util.Arrays;
  4.  
  5. class SinglyLinkedList {
  6.     private static class ListNode {
  7.         int value;
  8.         ListNode next;
  9.  
  10.         ListNode(int val) {
  11.             value = val;
  12.             next = null;
  13.         }
  14.     }
  15.  
  16.     private ListNode head;
  17.  
  18.     public SinglyLinkedList(ListNode head) {
  19.         this.head = head;
  20.     }
  21.  
  22.     /**
  23.      * 1→2→3→4→5→␀
  24.      */
  25.     static SinglyLinkedList makeList(int... values) {
  26.         ListNode head = null, prev = null;
  27.  
  28.         for (int v : values) {
  29.             ListNode current = new ListNode(v);
  30.             if (prev != null)
  31.                 prev.next = current;
  32.             else head = current;
  33.             prev = current;
  34.         }
  35.  
  36.         return new SinglyLinkedList(head);
  37.     }
  38.  
  39.     public void reverseList() {
  40.         reverseListResursive(head, head);
  41.     }
  42.  
  43.     private void reverseListResursive(final ListNode head, final ListNode node) {
  44.         final ListNode next = node.next;
  45.         if (next != null) {
  46.             if (next.next == null) {
  47.                 head.next.next = next;
  48.                 head.next = node;
  49.             }
  50.             reverseListResursive(head, next);
  51.             if (node != head && next.next != null)
  52.                 next.next = node;
  53.         } else {
  54.             final int value = node.value;
  55.             node.value = head.value;
  56.             head.value = value;
  57.         }
  58.     }
  59.  
  60.     public void printList() {
  61.         printList(this.head);
  62.     }
  63.  
  64.     static void printList(ListNode head) {
  65.         if (head == null)
  66.             System.out.println('␀');
  67.         else {
  68.             System.out.print(head.value);
  69.             System.out.print('→');
  70.             printList(head.next);
  71.         }
  72.     }
  73. }
  74.  
  75. public class Solution {
  76.     public static void main(String[] args) {
  77.         SinglyLinkedList list = SinglyLinkedList.makeList(Arrays.stream(args).mapToInt(Integer::parseInt).toArray());
  78.         list.printList();
  79.         list.reverseList();
  80.         list.printList();
  81.     }
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement