反转链表前n个节点和反转链表后n个节点

缺乏、安全感 2024-03-22 15:39 48阅读 0赞

### 反转链表前n个节点 ###

非递归方法：理解了全链表反转，该题只需要注意指针的处理。反转前n个节点，需要保存第n+1个节点，与反转后的前N个节点链表进行拼接。

class Solution {
        
        public ListNode reverseList(ListNode head,int n) {
        
            if(head == null){
        
                return null;
            }
            ListNode nNext = head;
            for(int i = 0;i<n;i++){
        
                nNext = nNext.next;
            }
            ListNode pre = null;
            ListNode cur = head;
            while(cur != nNext){
        
                ListNode temp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = temp;
            }
            head.next = nNext;
            return pre;
        }
    }

递归方法类似全链表反转，注意递归的终止条件

class Solution {
        
        public ListNode reverseList(ListNode head,int n) {
        
            if(head == null){
        
                return null;
            }
            ListNode precursor = null;
            if(n == 1){
        
                precursor = head.next;
                return head;
            }
            ListNode last = reverseList(head.next,n-1);
            head.next.next = head;
            head.next = precursor;
            return last;
        }
    }

### 反转链表后n个节点 ###

class Solution {
        
        public ListNode reverseList(ListNode head,int n) {
        
            if(head == null){
        
                return null;
            }
            //使用快慢指针
            ListNode slow = head;
            ListNode fast = head;
            for(int i = 0;i<n;i++){
        
                fast = fast.next;
            }
            while(fast.next != null){
        
                fast = fast.next;
                slow = slow.next;
            }
            ListNode cur = slow.next;
            ListNode pre = null;
            while(cur != null){
        
                ListNode temp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = temp;
            }
            slow.next = pre;
            return head;
    
        }