ReverseLinkedList(翻转链表)
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。非连续、非顺序指的是，通过指针把一组零散的内存块串联在一起，其中每一个内存块叫做链表的节点，所以每个节点包含两部分一个data（你存放的数据），一个next（指向下一个节点）当然这里使用单向链表举例。双向链表则有两个指向节点一个next（下一个节点）一个prev（上一个节点），对比：双向链表虽然更麻烦，但是比单向链表更受欢迎，因为，他记录了上一个节点，节省了操作数据时候的时间，但是需要用内存换时间。
单向链表：
双向链表；
题目一：
give a group of data, reverse it from end to head
Input: 1 ->2->3->4->5
Output: 5->4->3->2->1
tip： make 3 node to dominate data,To simulate a window to push the data then reverse the whole list, it is vital to change position of 3 node in list
/** * @author : lizi * @date : 2021-03-02 17:05 **/ public class ListNode { int val = 0; ListNode next; ListNode(int x) { val = x; } public void setVal(int val) { this.val = val; } public void setNext(ListNode next) { this.next = next; } }
private static ListNode reverseList(ListNode head) { if (head == null) return null; ListNode prev=head; ListNode current=head.next; // because the last Node point into null,so let fist node.next point into null prev.next=null; while (current!=null){ ListNode next=current.next; // that is place where change node. change position of current and prev current.next=prev; prev=current; // change current into next (in the way,the window is pushed) current=next; } return prev; } }
题目二：
obviously，we should change position of m and n
Input：1->2->3->4->5->null ,m=2,n=5
Output:1->4>3>2>5>null
tip: actually, many companies like to make this question as ultimate question,also the question was Amazon’s question for interviewee,however, we remain can use method in reversing whole linkedList. i mean that method of pushing window.
private static ListNode reverseBetween(ListNode head, int m, int n) { // if you can not find head, you can make the node.next to find head, todo actually, it is a node that prevent you can not find first node ListNode dummy = new ListNode(-1); dummy.next=head; head=dummy; // to find a place where you began to control list for (int i = 1; i <m ; i++) { head=head.next; } ListNode prevM=head; ListNode mNode=prevM.next; ListNode nNode=mNode; ListNode postN=nNode.next; //todo visibly, the portion is method of window that i mention in method of reversing the whole window for (int i = m; i <n ; i++) { ListNode next=postN.next; postN.next=nNode; nNode=postN; postN=next; } prevM.next=nNode; mNode.next=postN; // you can get dummy node.next in this way ,find the first node return dummy.next; }
finally: to do examine
public static void main(String[] args) { ListNode listNode1 = generateDate(); System.out.println(listNode1.toString()); // reverse whole list ListNode reverseBetween = reverseList(generateDate()); // reverse m and n in list ListNode listNode = reverseBetween(listNode1, 2, 4); printForSomething(reverseBetween); } // just to print result public static void printForSomething(ListNode listNode) { if (listNode != null) { System.out.println(listNode.val); printForSomething(listNode.next); } }
the picture is what i visualize method how to run:
To summarize:
as a beginner,personally, it is abstract to imagine how the cell of linkedlist connect with each other,but it is a effective to draw what you imagine. i still want everyone to criticize what i wrong in every article.
