【剑指offer-Java版】16反转链表

ゞ浴缸里的玫瑰 2022-08-21 08:58 24阅读 0赞

反转链表：此处为了符合题意就不设置头结点了  
思路简单直接，遍历一遍即可

需要注意的地方：  
输入异常：空或者只有一个结点

public class _Q16 {
        
    
        public ListNode ReverseList(ListNode list){
    
            if(list == null) return null;
            if(list.next == null) return list; // 只有一个结点直接返回
    
            ListNode nodePre = list;
            ListNode nodeNext = nodePre.next;
            ListNode node = nodeNext.next;
    
            // while循环结束之后nodeNext所指向的结点就是反转后的头结点
            // 画个图很容易明白-干巴巴的想总是容易想错
            nodePre.next = null; // 第一个结点的next需要置为空
            while(node != null){
                nodeNext.next = nodePre;
    
                nodePre = nodeNext;
                nodeNext = node;
                node = node.next;
            }
            nodeNext.next = nodePre; // 最后一个指针的时候node==null，所以需要单独连接
    
            return nodeNext;
        }
        }

测试代码：

public class _Q16Test extends TestCase {
        
    
        _Q16 reverse = new _Q16();
    
        public void test(){
            ListNode Head = new ListNode();
            ListNode NewHead = new ListNode();
    
            ListNode node1 = new ListNode();
            ListNode node2 = new ListNode();
            ListNode node3 = new ListNode();
            ListNode node4 = new ListNode();
    
            node1.value = 1;
            node2.value = 2;
            node3.value = 3;
            node4.value = 4;
    
            node1.next = node2;
            node2.next = node3;
            node3.next = node4;
            node4.next = null;
    
            Head.next = node1;
            CommonUtils.PrintList(Head);
            NewHead.next = reverse.ReverseList(node1);
            CommonUtils.PrintList(NewHead);
        }
        }