In this tutorial, we’ll implement two linked list reversal algorithms<\/a> in Java.<\/p>\n A linked list is a linear data structure in which a pointer in each element determines the order.\u00a0Each element of a linked list contains a data field to store the list data and a pointer field to point to the next element in the sequence.<\/strong> Also, we can use a head<\/em> pointer to point to the start element of a linked list:<\/p>\n After we reverse the linked list, the head<\/em> will point to the last element of the original linked list, and the pointer of each element will point to the previous element of the original linked list:<\/p>\n In Java, we have a LinkedList<\/a> <\/em>class to provide a\u00a0doubly-linked list implementation of the\u00a0List<\/em>\u00a0and\u00a0Deque<\/em> interfaces. However, we’ll use a general singly-linked list data structure in this tutorial.<\/p>\n Let’s first start with a ListNode<\/em> class to represent an element of a linked list:<\/p>\n The ListNode\u00a0<\/em>class has two fields:<\/p>\n A linked list may contain multiple ListNode<\/em> objects. For example, we can construct the above sample linked list with a loop:<\/p>\n Let’s implement the iterative algorithm<\/a> in Java:<\/p>\n In this iterative algorithm, we use two ListNode<\/em> variables, previous<\/em> and current<\/em>, to represent two adjacent elements in the linked list. For each iteration, we reverse these two elements and then shift to the next two elements.<\/p>\n In the end, the current <\/em>pointer will be null,<\/em> and the previous<\/em> pointer will be the last element of the old linked list. Therefore, previous\u00a0<\/em>is also the new head pointer of the reversed linked list, and we return it from the method.<\/p>\n We can verify this iterative implementation with a simple unit test:<\/p>\n In this unit test, we first construct a sample linked list with five nodes. Also, we verify that each node in the linked list contains the correct data value. Then, we call the iterative function to reverse the linked list. Finally, we check the reversed linked list to make sure the data are reversed as expected.<\/p>\n Now, let’s implement the recursive algorithm<\/a> in Java:<\/p>\n In the reverseListRecursive <\/em>function, we recursively visit each element in the linked list until we reach the last one. This last element will become the new head of the reversed linked list. Also, we append the visited element to the end of the partially reversed linked list.<\/p>\n Similarly, we can verify this recursive implementation with a simple unit test:<\/p>\n In this tutorial, we implemented two algorithms to reverse a linked list. As always, the source code for the article is available\u00a0over on GitHub<\/a>.<\/p>\n The post Reversing a Linked List in Java<\/a> first appeared on Baeldung<\/a>.<\/p>\n Implement two linked list reversal algorithms in Java<\/p>\n The post Reversing a Linked List in Java<\/a> first appeared on Baeldung<\/a>.<\/p>\n2. Linked List Data Structure<\/b><\/strong><\/h2>\n
![\"\"](\"http:\/\/www.baeldung.com\/wp-content\/uploads\/2020\/09\/linkedlist.png\")
<\/a><\/p>\n![\"\"](\"https:\/\/www.baeldung.com\/wp-content\/uploads\/2020\/09\/reversedlinkedlist1.png\")
<\/a><\/p>\npublic class ListNode {\r\n private int data;\r\n private ListNode next;\r\n ListNode(int data) {\r\n this.data = data;\r\n this.next = null;\r\n }\r\n \/\/ standard getters and setters\r\n}<\/code><\/pre>\n\n
ListNode constructLinkedList() {\r\n ListNode head = null;\r\n ListNode tail = null;\r\n for (int i = 1; i <= 5; i++) {\r\n ListNode node = new ListNode(i);\r\n if (head == null) {\r\n head = node;\r\n } else {\r\n tail.setNext(node);\r\n }\r\n tail = node;\r\n }\r\n return head;\r\n}<\/code><\/pre>\n3. Iterative Algorithm Implementation<\/b><\/strong><\/h2>\n
ListNode reverseList(ListNode head) {\r\n ListNode previous = null;\r\n ListNode current = head;\r\n while (current != null) {\r\n ListNode nextElement = current.getNext();\r\n current.setNext(previous);\r\n previous = current;\r\n current = nextElement;\r\n }\r\n return previous;\r\n}<\/code><\/pre>\n@Test\r\npublic void givenLinkedList_whenIterativeReverse_thenOutputCorrectResult() {\r\n ListNode head = constructLinkedList();\r\n ListNode node = head;\r\n for (int i = 1; i <= 5; i++) {\r\n assertNotNull(node);\r\n assertEquals(i, node.getData());\r\n node = node.getNext();\r\n }\r\n \r\n LinkedListReversal reversal = new LinkedListReversal();\r\n node = reversal.reverseList(head);\r\n \r\n for (int i = 5; i >= 1; i--) {\r\n assertNotNull(node);\r\n assertEquals(i, node.getData());\r\n node = node.getNext();\r\n }\r\n}<\/code><\/pre>\n4. Recursive\u00a0Algorithm Implementation<\/b><\/strong><\/h2>\n
ListNode reverseListRecursive(ListNode head) {\r\n if (head == null) {\r\n return null;\r\n }\r\n if (head.getNext() == null) {\r\n return head;\r\n }\r\n ListNode node = reverseListRecursive(head.getNext());\r\n head.getNext().setNext(head);\r\n head.setNext(null);\r\n return node;\r\n}<\/code><\/pre>\n@Test\r\npublic void givenLinkedList_whenRecursiveReverse_thenOutputCorrectResult() {\r\n ListNode head = constructLinkedList();\r\n ListNode node = head;\r\n for (int i = 1; i <= 5; i++) {\r\n assertNotNull(node);\r\n assertEquals(i, node.getData());\r\n node = node.getNext();\r\n }\r\n \r\n LinkedListReversal reversal = new LinkedListReversal();\r\n node = reversal.reverseListRecursive(head);\r\n \r\n for (int i = 5; i >= 1; i--) {\r\n assertNotNull(node);\r\n assertEquals(i, node.getData());\r\n node = node.getNext();\r\n }\r\n}<\/code><\/pre>\n5. Conclusion<\/strong><\/h2>\n
<\/p>\n
![](\"https:\/\/assets.feedblitz.com\/i\/fblike20.png\")
<\/a> ![](\"https:\/\/assets.feedblitz.com\/i\/googleplus20.png\")
<\/a> ![](\"https:\/\/assets.feedblitz.com\/i\/pinterest20.png\")
<\/a> ![](\"https:\/\/assets.feedblitz.com\/i\/twitter20.png\")
<\/a> ![](\"https:\/\/assets.feedblitz.com\/i\/email20.png\")
<\/a> ![](\"https:\/\/assets.feedblitz.com\/i\/rss20.png\")
<\/a> ![](\"https:\/\/assets.feedblitz.com\/i\/comments20.png\")
<\/a> ![](\"https:\/\/assets.feedblitz.com\/i\/commentsrss20.png\")
<\/a> <\/div>\n\n![\\\"IT\u96fb\u8166\u88dc\u7fd2](\\\"http:\/\/itteacheritfreelance.hk\/test\/wordpress\/wp-content\/uploads\/2016\/05\/logo2-2.png\\\"){kind=logo}
\r\nwww.itsec.hk<\/a>
\r\nwww.itsec.vip<\/a>
\r\nwww.itseceu.uk<\/a>
<\/p>","protected":false},"excerpt":{"rendered":"<\/a> <\/a> <\/a> <\/a> <\/a> <\/a> <\/a> <\/a> <\/div>\n<\/div>","protected":false},"author":914,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"slim_seo":{"title":"Reversing a Linked List in Java - ITTeacherITFreelance.hk","description":"Implement two linked list reversal algorithms in Java The post Reversing a Linked List in Java first appeared on Baeldung . &"},"footnotes":""},"categories":[6],"tags":[],"_links":{"self":[{"href":"https:\/\/itteacheritfreelance.hk\/wordpress\/index.php\/wp-json\/wp\/v2\/posts\/83445"}],"collection":[{"href":"https:\/\/itteacheritfreelance.hk\/wordpress\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/itteacheritfreelance.hk\/wordpress\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/itteacheritfreelance.hk\/wordpress\/index.php\/wp-json\/wp\/v2\/users\/914"}],"replies":[{"embeddable":true,"href":"https:\/\/itteacheritfreelance.hk\/wordpress\/index.php\/wp-json\/wp\/v2\/comments?post=83445"}],"version-history":[{"count":5,"href":"https:\/\/itteacheritfreelance.hk\/wordpress\/index.php\/wp-json\/wp\/v2\/posts\/83445\/revisions"}],"predecessor-version":[{"id":85413,"href":"https:\/\/itteacheritfreelance.hk\/wordpress\/index.php\/wp-json\/wp\/v2\/posts\/83445\/revisions\/85413"}],"wp:attachment":[{"href":"https:\/\/itteacheritfreelance.hk\/wordpress\/index.php\/wp-json\/wp\/v2\/media?parent=83445"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/itteacheritfreelance.hk\/wordpress\/index.php\/wp-json\/wp\/v2\/categories?post=83445"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/itteacheritfreelance.hk\/wordpress\/index.php\/wp-json\/wp\/v2\/tags?post=83445"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}