【剑指Offer题解：java】反转链表

今天药忘吃喽~ 2023-01-07 10:14 90阅读 0赞

> *输入一个链表，反转链表后，输出新链表的表头。*

## 思路一： ##

新建一个头结点，遍历原链表，每遍历一个节点，就将新的节点插入到头结点的后面

注意链表的保存

![image.png][]

public static ListNode ReverseList(ListNode head) { 
            if(head == null||head.next == null)return head;//如果只有一个节点，不需要转换
            ListNode tempHead = new ListNode(0);//辅助头结点
    
            ListNode cur = head;//原链表辅助指针
            ListNode next = null;//保存后面的链表
            while (true){ 
                if(cur == null)break;
                next = cur.next;//保存后面的链表
                cur.next = tempHead.next;
                tempHead.next = cur;
                //原链表向后挪动
                cur = next;
            }
    
            return tempHead.next;
        }

## 思路二： ##

1.  使用栈，遍历第一遍，将所有节点依次放入栈中
2.  依次弹栈，组成新的链表即可

/** * 使用栈实现单链表的反转 * 1、将链表放入栈中 * 2、一次从栈中取出够成一个新的链表即可 */
        public void reverseLinkedByStack() { 
            if (HeadNode.next == null) { 
                System.out.println("当前链表为空");
                return;
            }
            Node temp = HeadNode.next;
            Stack<Node> stack = new Stack<>();
            //遍历链表，放入栈中
            while (true) { 
                stack.push(temp);
                if (temp.next == null) break;
                temp = temp.next;
            }
            //遍历完成后，逐个弹栈，重新构成新的链表即可
            temp = HeadNode;
            while (!stack.empty()) { 
                temp.next = stack.pop();
                temp = temp.next;
            }
            temp.next = null;//最后一个元素next域置为空
        }

[image.png]: /images/20221119/f896e58476e642f0bc56031acdbef7cd.png