java实现琏表逆序

╰+哭是因爲堅強的太久メ 2022-03-15 06:06 144阅读 0赞

题目：将一个有链表头的单向单链表逆序

分析：

1.  链表为空或只有一个元素直接返回；
2.  设置两个前后相邻的指针p,q，使得p指向的节点为q指向的节点的后继；
3.  重复步骤2，直到q为空；
4.  调整链表头和链表尾；

图解：

以链表A->B->C->D为例，逆序此链表。

0.初始状态                                                        1.2.3 循环部分

p = head->next;                                              while(q!=null)\{

q = head->next->next;                                    　　t = q->next;

t = null;                                                          　　q->next = p;

p = q;

q = t;

0.初始状态

![031405076457217.jpg][]

1.第一次循环

![031418429113583.jpg][]

2.第二次循环

![031421331458541.jpg][]

3.第三次循环

![031422513025597.jpg][]

4.q==null循环结束

head->next->next = null;//设置链表尾

head-next = p;//修改链表头

![031432470999511.jpg][]

实现及测试代码

节点Node类：

![复制代码][copycode.gif]

package linkList.reverse;
    
    /**
     * 链表节点
     * @author Administrator
     *
     */
    public class Node {
        private Integer data;//节点数据域
        private Node next;//节点指针域
        public Integer getData() {
            return data;
        }
        public void setData(Integer data) {
            this.data = data;
        }
        public Node getNext() {
            return next;
        }
        public void setNext(Node next) {
            this.next = next;
        }
    }

![复制代码][copycode.gif]

逆序方法：

![复制代码][copycode.gif]

/**
         * 
         * @param node 原始链表头节点
         * @return 逆序后链表头节点
         */
         Node reverseList(Node head){
            //如果链表为空或只有一个元素直接返回
            if(head.getNext()==null||head.getNext().getNext()==null){
                return head;
            }
            Node p = head.getNext();
            Node q = head.getNext().getNext();
            Node t = null;
            while(q!=null){
                t = q.getNext();
                q.setNext(p);
                p = q;
                q = t;
            }
            //设置链表尾
            head.getNext().setNext(null);
            //修改链表头
            head.setNext(p);
            return head;
        }

![复制代码][copycode.gif]

测试代码：

![复制代码][copycode.gif]

//表头
            Node head = new Node();
            head.setData(-1);
            head.setNext(null);
            
            //定义指针
            Node p;
            
            p = head;
            
            //初始化链表数据[1~10]
            for(int i=1;i<=10;i++){
                Node q = new Node();
                q.setData(i);
                q.setNext(null);
                p.setNext(q);
                p = q;
            }
            
            //输出原始链表
            printList(head);
            
            System.out.println("");
            
            //输出逆序后的链表
            printList(reverseList(head));

![复制代码][copycode.gif]

关注公众号，我们来聊一聊java

![20190303185840292.jpg][]

[031405076457217.jpg]: /images/20220315/a134fbfb16d24a449a3b1d57a7907cc4.png
[031418429113583.jpg]: /images/20220315/af59d59bf0db46dfa6e1e7e869e246d6.png
[031421331458541.jpg]: /images/20220315/50be1bc57ed141ceb077079adc38b1f5.png
[031422513025597.jpg]: /images/20220315/3f039f788255417bb18b3c9bee285e78.png
[031432470999511.jpg]: /images/20220315/c811a32144cf4babb57115a9ce4e375e.png
[copycode.gif]: /images/20220315/25640be0993b4632bb5413f740bbac64.png
[20190303185840292.jpg]: /images/20220315/713a3ebbba5348958b9d30c3046eac94.png