reverseLinkedList(翻转链表)

时间:2021-03-15 UpGx 人气:0

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.

加载全部内容