【LC总结】翻转链表 Swap in Pairs, Reverse in k-Group, Reverse LinkedList

梦里梦外; 2022-02-21 13:07 116阅读 0赞

# Swap Nodes in Pairs #

For example,  
Given 1->2->3->4, you should return the list as 2->1->4->3.

## Solution ##

public class Solution {
        public ListNode swapPairs(ListNode head) {
            if (head == null || head.next == null) return head;
            ListNode dummy = new ListNode(0);
            dummy.next = head;        
            ListNode cur = dummy;
            while (cur.next != null && cur.next.next != null) {
                ListNode n1 = cur.next;
                ListNode n2 = cur.next.next;
                cur.next = n2;
                n1.next = n2.next;
                n2.next = n1;
                cur = n1;
            }
            return dummy.next;
        }
    }

# Reverse Nodes in k-Group #

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.  
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.  
You may not alter the values in the nodes, only nodes itself may be changed.  
Only constant memory is allowed.

For example,  
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

## Solution ##

public class Solution {
        public ListNode reverseKGroup(ListNode head, int k) {
            if (head == null || head.next == null || k == 0) return head;
            ListNode start = head, end = head;
            int count = k-1;
            while (count != 0 && end.next != null) {
                end = end.next;
                count--;
            }
            if (count == 0) {
                ListNode next = end.next;
                reverse(start, end);
                start.next = reverseKGroup(next, k);
                return end;
            }
            else return start;
        }
        public void reverse(ListNode start, ListNode end) {
            ListNode pre = null;
            while (start != end) {
                ListNode next = start.next;
                start.next = pre;
                pre = start;
                start = next;
            }
            start.next = pre;
        }
    }

# Reverse Linked List #

Reverse a singly linked list.

## Note ##

Create tail = null;  
Head loop through the list: Store head.next, head points to tail, tail becomes head, head goes to stored head.next;  
Return tail.

## Solution ##

public class Solution {
        public ListNode reverseList(ListNode head) {
            ListNode tail = null;
            while (head != null) {
                ListNode temp = head.next;
                head.next = tail;
                tail = head;
                head = temp;
            }
            return tail;
        }
    }

# Reverse Linked List II #

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

## Note: ##

Given m, n satisfy the following condition:  
1 ≤ m ≤ n ≤ length of list.

## Solution ##

public class Solution {
        public ListNode reverseBetween(ListNode head, int m, int n) {
            if (head == null) return null;
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            ListNode pre = dummy;
            int i = 0;
            while (i++ < m-1) {//注意这里，pre只要走到第m-1位
                pre = pre.next;
            }
            ListNode cur = pre.next;
            ListNode next = pre.next.next;
            for (i = 0; i < n-m; i++) {
                cur.next = next.next;
                next.next = pre.next;
                pre.next = next;
                next = cur.next;
            }
            return dummy.next;
        }
    }