ReverseLinkedList(翻转链表)

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。非连续、非顺序指的是，通过指针把一组零散的内存块串联在一起，其中每一个内存块叫做链表的节点，所以每个节点包含两部分一个data（你存放的数据），一个next（指向下一个节点）当然这里使用单向链表举例。双向链表则有两个指向节点一个next（下一个节点）一个prev（上一个节点），对比：双向链表虽然更麻烦，但是比单向链表更受欢迎，因为，他记录了上一个节点，节省了操作数据时候的时间，但是需要用内存换时间。

单向链表：

双向链表；

题目一：

给定一组数据，从尾到头进行翻转

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

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

思路：使用是三个变量进行控制（prev、current、next），模拟一个窗口，进行对数据的推进，进而翻转，不断改变三个元素的位置。

/**

 * @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.

巴特西

reverseLinkedList(翻转链表)

ReverseLinkedList(翻转链表)

最新文章

热门文章