Shulou(Shulou.com)05/31 Report--

This article introduces the relevant knowledge of "how to flip the linked list in Java". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Package com.lifeibigdata.algorithms.leetcode;/** * Created by lifei on 16-6-30. * / public class ReverseListNode {public static void main (String [] args) {ListNode head=new ListNode (1); ListNode N1 = new ListNode (2); ListNode N2 = new ListNode (3); ListNode n3 = new ListNode (4); / / initialize the linked list head.next = N1; n1.next = N2; n2.next = n3; System.out.println ("before print linked list is reversed:") Utils.print (head); ReverseListNode rln = new ReverseListNode (); System.out.println ("print the linked list reversed:"); ListNode newHead = rln.reverse4 (head); / / TODO 3 ways Utils.print (newHead); / / System.out.println ("= create="); / / ListNode cln = createList (new int [] {1jor2jin3); / / Utils.print (cln) } / * first round * 3.next (reverse) revHead 4 * 3.next.next=4.next (null before assignment) 3 * 3.next-> null * 4 3 null * * second round * 2.next.next=3.next (null before assignment) 2 * 2.next-> null * 4 32 null * * @ param head * @ return * / ListNode reverse (ListNode head) {if (null = = head | | null = = head.next) {/ / TODO if it is the end node The endpoint will be returned, so revHead is the endpoint return head } ListNode revHead = reverse (head.next); System.out.println ("-" + head.val+ "," + head.next.val+ "-"); head.next.next = head; / / 3.next.next (4.next, where 4 is the flipped head node) = 3 head.next = null; / / 3.next=null return revHead } / / description of the idea of "headline insertion": starting from the first node of the linked list, each node is used as a unit to traverse the linked list, and the traversed nodes are successively inserted into the back of the header node ListNode reverse2 (ListNode head) {/ / TODO if (null = = head | | null = = head.next) {return head;} ListNode pre = null / / the header node ListNode cur = head; / / cur in the process of the new linked list is the cursor that traverses, and the header node ListNode next = cur.next; while (next! = null) {/ / todo cur is the node to be inserted. Here is the condition for judging the termination of the loop cur.next = pre. / / pre the node to be inserted-> the header node of the new linked list pre = cur; / / take the newly inserted node as the header node of the next loop cur = next; / / cycle the next node next = cur.next; / / determine the next node of the new node, cycle} node = pre Return cur;} / / plug-in static ListNode reverse3 (ListNode head) {if (null = = head | | null = = head.next) {return head;} ListNode nextHead = null; / / next node to be transferred ListNode newHead = null; / / head node of the new chain ListNode newn = null / / the node to be inserted requires the node to be inserted to point directly to the head node of the new chain, then the newly inserted node is returned, that is, the chain head node newHead = head; / / assign the old header node to the new header node head = head.next / / head is already the second node newHead.next = null; while (head.next! = null) {/ / at this time head is the second node, which is the new node that needs to be added to the linked list, that is, the third node of newn; head.next, nextHead = head.next; / / the node to be transferred next time newn = head / / the new node to be inserted newn.next = newHead; / / the newly inserted node points to the head node of the new chain newHead = newn; / / use the newly inserted node as the node of the new chain / / newn.next = newHead.next / / wrong cannot be used to create a linked list, because the way to create a linked list has an empty header node / / newHead.next = newn; / / wrong head = nextHead;} newn = head / / because each time the next node of the newly inserted node is judged, the last node is not in the loop, and the head is the last node newn.next = newHead; return newn;} ListNode reverse4 (ListNode L) {/ / TODO ListNode head = null; ListNode temp; while (L! = null) {temp = L.next / / assign the second node to tmp L.next = head;//, point the first node to the new header node head = L; / / assign the new header node L to head for the next cycle L = temp; / / the second node} return head in the next iteration } / * figure * @ param head * @ return * / ListNode reverse5 (ListNode head) {/ / TODO ListNode pRerverseHead = null; ListNode pNode = head; ListNode pPrev = null; while (pNode! = null) {ListNode next = pNode.next; if (next = = null) {pRerverseHead = pNode } pNode.next = pPrev; pPrev = pNode; pNode = next;} return pRerverseHead;} static ListNode createList (int [] values) {ListNode head = new ListNode (0); for (int I = 0 new ListNode I)

< values.length;i++){ ListNode node = new ListNode(values[i]);//新节点node node.next = head.next;//将头节点的尾部转移到新节点的尾部 head.next = node;//将头结点尾部指向新节点 } return head.next; } /** * * 打印链表反转前： 1->

2-> 3-> 4-> after the print chain list has been reversed:-4Mae 3murmuri If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.