leetcode 206. 反转链表（Java）

浅浅的花香味﹌ 2022-03-10 11:20 134阅读 0赞

*  链表反转示意图如下：
    
        输入: 1->2->3->4->5->NULL
        输出: 5->4->3->2->1->NULL
 *  思路：从头结点开始一个个节点反转，反转每个节点时需要保存自身节点引用backward和自身的下一个节点引用forward，保存好之后，则反转当前节点。然后开始第二个节点的反转，即迁移自身到原来的下一个节点，即与forward指向同一个节点，此时可以前移forward到下一个节点，即第三个节点。然后反转当前节点（即第二个节点）指向前一个节点backward（即第一个节点），并前移backward指向当前节点（即第二个节点），此时第二个节点反转完成。
 *  接着以以上步骤继续反转第三个节点，直到尾节点，源码如下：
    
        /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
        class Solution { 
            public ListNode reverseList(ListNode head) { 
                if (head == null) { 
                    return head;
                }
                
                // 反转每个节点时，需要保存当前节点和当前节点的下一个节点后，才对当前节点进行反转
                ListNode backward = head;
                ListNode forwad =  head.next;
                
                // 此时可以反转head的next为null了
                head.next = null;
                
                while (forwad != null) { 
                    head = forwad; // head执行原先的head.next
                    forwad = head.next; // forward指向head.next.next
                    
                    // 此时实现head.next的反转，指向head
                    head.next = backward; // head.next执行head，完成了head.next的反转
                    backward = head; // backward执行head.next
                }
                return head;
            }
        }