【LC總結】翻轉鏈表 Swap in Pairs, Reverse in k-Group, Reve

Steve_Wang_ 發布于2019-08-14 14:55 / 1942人閱讀

摘要：注意這里，只要走到第位

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;
    }
}

GPU云服務器云服務器 INS In in 域名 in 后綴域名

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65185.html

[Leetcode] Swap Nodes in Pairs Reverse Nodes in k-

摘要：三指針法復雜度時間空間思路基本的操作鏈表，見注釋。注意使用頭節點方便操作頭節點。翻轉后，開頭節點就成了最后一個節點。 Swap Nodes in Pairs Given a linked list, swap every two adjacent nodes and return its head. For example, Given 1->2->3->4, you should ...

TZLLOG 2019-08-14 12:45 評論0 收藏0
y-a-b-e

摘要：算法鏈表總結翻轉鏈表二叉樹數搜索區間矩陣走法，數組矩陣字符串一個數組能否分成兩堆數，使兩堆數的和相等先求總和，若有一堆數，和為，那么就沒問題。算法鏈表【LC總結】翻轉鏈表 Swap in Pairs, Reverse in k-Group, Reverse LinkedList###Reverse a doubly linkedlist reverse singly linked...

Terry_Tai 2019-08-14 14:57 評論0 收藏0
leetcode 24 Swap Nodes in Pairs

摘要：最后返回頭節點。同時題目要求只能占用常數空間，并且不能改變節點的值，改變的是節點本身的位置。翻轉是以兩個節點為單位的，我們新聲明一個節點表示當前操作到的位置。每次操作結束，將指針后移兩個節點即可。執行操作前要確定操作的兩個節點不為空。題目詳情 Given a linked list, swap every two adjacent nodes and return its head....

heartFollower 2019-08-15 14:44 評論0 收藏0
leetcode24 Swap Nodes in Pairs 交換鏈表中相鄰兩個節點

摘要：題目要求翻譯過來就是將鏈表中相鄰兩個節點交換順序，并返回最終的頭節點。思路這題的核心解題思路在于如何不占用額外的存儲空間，就改變節點之間的關系。題目要求 Given a linked list, swap every two adjacent nodes and return its head. For example, Given 1->2->3->4, you should r...

GT 2019-08-14 18:13 評論0 收藏0