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

Steve_Wang_ 发布于2019-08-14 14:55 / 1941人阅读

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

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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