链表全部翻转、翻转前n个元素（双指针法，O(n)时间复杂度 O(1)空间复杂度）

不念不忘少年蓝@ 2024-03-27 07:26 6阅读 0赞

> 给你一个单链表，请将其翻转。  
> 我们使用双指针法进行翻转，仅需要遍历一次。

*  链表节点类，自写的

package link;
    
    /**
     * link list node class
     * @author humorchen
     * @date 2023/1/31 14:43
     */
    public class Node {
        
        public int val;
        public Node next;
    }

*  链表辅助类，自己写的

package link;
    
    /**
     * util for link list
     * @author humorchen
     * @date 2023/1/31 14:44
     */
    public class LinkListUtil {
        
        /**
         * 生成链表
         * @param len
         * @return
         */
        static Node newList(int len) {
        
            Node head = null, p = null;
            while (len > 0) {
        
                Node node = new Node();
                node.val = len;
                if (p == null) {
        
                    head = node;
                } else {
        
                    p.next = node;
                }
                p = node;
                --len;
            }
            return head;
        }
    
        /**
         * 打印链表
         * @param head
         */
        static void print(Node head) {
        
            Node p = head;
            System.out.print("link list：");
            while (p != null) {
        
                System.out.print(p.val + " ");
                p = p.next;
            }
            System.out.println();
        }
    }

*  翻转整个链表

> link list：10 9 8 7 6 5 4 3 2 1  
> link list：1 2 3 4 5 6 7 8 9 10

/**
     * reverse a node list
     * @author humorchen
     * @date 2023/1/31 14:21
     */
    public class ReverseLinkList {
        
        public static void main(String[] args) {
        
            // 产生一个链表
            Node list = LinkListUtil.newList(10);
            // 打印该链表
            LinkListUtil.print(list);
            // 翻转链表
            Node reversedList = reverse(list);
            // 打印翻转后的链表
            LinkListUtil.print(reversedList);
        }
    
        /**
         * 将链表翻转
         * @param head
         * @return
         */
        static Node reverse(Node head) {
        
            // pre为前一个节点（想象的），cur为当前节点，从头结点开始遍历
            Node pre = null, cur = head;
            // 当前节点不为空，则继续遍历
            while (cur != null) {
        
                // 临时存储好下一个节点以免丢失
                Node next = cur.next;
                // 当前节点等于前一个节点（翻转动作）
                cur.next = pre;
                // 当前节点成为前一个节点
                pre = cur;
                // 游标向下一个节点移动
                cur = next;
            }
            // cur为空，pre则为原链表里最后一个节点，也就是翻转后链表的头结点
            return pre;
        }
    
    
    }

*  翻转前n个节点

> 翻转前4个  
> link list：10 9 8 7 6 5 4 3 2 1  
> link list：7 8 9 10 6 5 4 3 2 1

/**
     * reverse a part(nth) of a link list
     * @author humorchen
     * @date 2023/1/31 14:41
     */
    public class ReversePartOfLinkList {
        
        public static void main(String[] args) {
        
            //生成链表
            Node head = LinkListUtil.newList(10);
            // 打印链表
            LinkListUtil.print(head);
            // 要翻转前多少个
            int n = 4;
            // 翻转处理
            Node newHead = reverse(head, n);
            // 打印翻转后的链表
            LinkListUtil.print(newHead);
        }
    
        /**
         * 翻转链表前n个节点
         * @param head
         * @param n
         * @return
         */
        static Node reverse(Node head, int n) {
        
            // 特殊情况处理
            if (head == null) {
        
                return null;
            }
            // pre为上一个节点，cur为当前节点，是个游标
            Node pre = null, cur = head;
            // 当前节点不为空，且还需要翻转n个
            while (cur != null && n > 0) {
        
                // 提前存储游标下一个节点，以免操作时丢失
                Node next = cur.next;
                //  当前节点的next设置为前一个节点（翻转操作）
                cur.next = pre;
                // 当前节点成为pre节点
                pre = cur;
                // 当前游标节点cur向右移动
                cur = next;
                // 还需要翻转的个数自减
                --n;
            }
            // 翻转后的前n个元素的子链表与切割处的节点进行拼接（cur已经到了翻转后的下一个节点了，head是翻转后链表的最后一个节点）
            head.next = cur;
            return pre;
        }
    }