给出索引,k可能非常大 最好不要申请额外空间

作者: 编程  发布:2019-08-28

LeetCode Rotate List

LeetCode Reverse Linked List II

在链表中穿针引线

链表和数组都是线性结构,但是链表和数组的不同在于数组可以随机的对于数据进行访问。给出索引。可以以O(1)的时间复杂度迅速访问到该元素。
链表只能从头指针开始。

next指针指向哪里?

206. Reverse Linked List

反转一个链表

链表反转

不能改变链表值。操作每个节点的next指针。
5的指针指向空的。变成指向4的。

next改变示意图

把1指向NUll之前要保存next指针

添加pre指针保存上一个节点

// 时间复杂度: O(n)
// 空间复杂度: O(1)
class Solution {
public:
    ListNode* reverseList(ListNode* head) {

        ListNode* pre = NULL;
        ListNode* cur = head;
        while( cur != NULL ){
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }

        return pre;
    }
};

92. Reverse Linked List II

反转一个链表从m到n的元素。

  • 如对于链表 1->2->3->4->5->NULL, m = 2 , n = 4
  • 则返回链表 1->4->3->2->5->NULL
    • m和n超过链表范围怎么办?
    • m > n 怎么办?

翻转m到n的元素。

LeetCode -- Rotate List

题目描述:

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

就是将倒数K个节点放在链表前。

思路:

  1. 遍历链表判断长度len是否小于k,如果是,则k = k % len
  2. 如果len = k或len < 2或k < 1,直接返回
  3. 遍历链表,移动len - k - 1个位置,存当前位置为q
  4. 将q之后的节点存入stack
  5. 遍历stack,依次将节点设为头结点
  6. 最后,将q.next指向Null

实现代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode RotateRight(ListNode head, int k) 
    {
        if(head == null){
      return null;
     }
        var len = LenOf(head);
     if(len < 2 || k == len || k < 1){
      return head;
     }
     if(k > len){
      k = k % len;
     }

     var stack = new Stack();
     var p = head;

     for(var i = 0;i < len - k - 1;i   ){
      p = p.next;
     }

     var q = p;

     p = p.next;
     while(p != null){
      stack.Push(p.val);
      p = p.next;
     }
     q.next = null;

     while(stack.Count > 0)
     {
      var n = new ListNode(stack.Pop());
      n.next = head;
      head = n;
     }

     return head;
    }


private int LenOf(ListNode head)
{
 var p = head;
 var len = 0;
 while(p != null){
  len   ;
  p = p.next;
 }
 return len;
}
}

 

-- Rotate List 题目描述: Given a list, rotate the list to the right by k places, where k is non-negative. For example: Given 1-2-3-4-5-NULL and k = 2, return 4-5-1-2...

LeetCode解题之Rotate List


LeetCode解题之Reverse Linked List II


测试链表程序。

写根据数组创建链表和打印链表两个函数

/// LinkedList Test Helper Functions
ListNode* createLinkedList(int arr[], int n){

    if( n == 0 )
        return NULL;

    ListNode* head = new ListNode(arr[0]);
    ListNode* curNode = head;
    for( int i = 1 ; i < n ; i    ){
        curNode->next = new ListNode(arr[i]);
        curNode = curNode->next;
    }

    return head;
}

void printLinkedList(ListNode* head){

    ListNode* curNode = head;
    while( curNode != NULL ){
        cout << curNode->val << " -> ";
        curNode = curNode->next;
    }

    cout<<"NULL"<<endl;

    return;
}

void deleteLinkedList(ListNode* head){

    ListNode* curNode = head;
    while( curNode != NULL ){
        ListNode* delNode = curNode;
        curNode = curNode->next;
        delete delNode;
    }

    return;
}

main.cpp:

int main(){

    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr)/sizeof(int);

    ListNode* head = createLinkedList(arr, n);
    printLinkedList(head);

    ListNode* head2 = Solution().reverseList(head);
    printLinkedList(head2);

    deleteLinkedList(head2);

    return 0;
}

运行结果

83. Remove Duplicates from Sorted List

给出一个有序链表,删除其中所有重复元素,使得每个元素只保留一次。

  • 如 1->1->2,返回1->2
  • 如 1->1->2->3->3,返回1->2->3

86. Partition List

给出一个链表以及一个数x,将链表重新整理,使得小于x的元素在前;大于等于x的元素在后。

  • 如 1->4->3->2->5->2,x=3
  • 返回 1->2->2->4->3->5

328. Odd Even Linked List

给出一个链表,将链表重新整理,使得所有索引为奇数的节点排在索引为偶数的节点前面。

  • 如 1->2->3->4->5->NULL
  • 返回 1->3->5->2->4->NULL
  • 第一个节点的索引为1
  • 奇数索引的节点和偶数索引的节点在重新整理后要保持相对顺序。

2. Add Two Numbers

给出两个非空链表,表示两个非负整数。其中每一个整数的各位数字以逆序存储,返回这两个整数相加所代表的链表。

  • 如 342 465 = 807
  • 则给出 2->4->3 和 5->6->4,返回7->0->8

数字中是否有前置的0。(除0以外,没有前置0)
负数?

445. Add Two Numbers II

给出两个非空链表,表示两个非负整数。其中每一个整数的各位数字以顺序存储,返回这两个整数相加所代表的链表。

  • 如 342 465 = 807
  • 则给出 3->4->2 和 4->6->5,返回8->0->7

如果不允许修改输入的链表呢?

使用辅助数据结构

原题

将一个链表中的元素向右旋转k个位置。

注意点:

k可能非常大 最好不要申请额外空间

例子:

输入: list = 1->2->3->4->5->NULL, k = 2

输出: 4->5->1->2->3->NULL

原题

在只遍历一遍且不申请额外空间的情况下将一个链表的第m到n个元素进行翻转。

注意点:

m和n满足如下条件:1 ≤ m ≤ n ≤链表长度

例子:

输入: 1->2->3->4->5->NULL, m = 2, n = 4

输出: 1->4->3->2->5->NULL

设立链表的虚拟头结点

203. Remove Linked List Elements

在链表中删除值为val的所有节点

  • 如 1->2->6->3->4->5->6->NULL,要求删除值为6的节点
  • 返回 1->2->3->4->5->NULL

删除节点

该逻辑对删除最后一个元素依然适用

该逻辑对删除第一个元素不适用

// 不使用虚拟头结点
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {

        while( head != NULL && head->val == val ){

            ListNode* node = head;
            head = head->next;
            delete node;
        }

        if( head == NULL )
            return head;

        ListNode* cur = head;
        while( cur->next != NULL ){

            if( cur->next->val == val ){
                ListNode* delNode = cur->next;
                cur->next = delNode->next;
                delete delNode;
                //delNode -> next = NULL;
            }
            else
                cur = cur->next;
        }

        return head;
    }
};

虚拟头结点

具体实现:

// 使用虚拟头结点
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {

        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;

        ListNode* cur = dummyHead;
        while( cur->next != NULL ){

            if( cur->next->val == val ){
                ListNode* delNode = cur->next;
                cur->next = delNode->next;
                delete delNode;
            }
            else
                cur = cur->next;
        }

        ListNode* retNode = dummyHead->next;
        delete dummyHead;

        return retNode;
    }
};

int main() {

    int arr[] = {1, 2, 6, 3, 4, 5, 6};
    int n = sizeof(arr)/sizeof(int);

    ListNode* head = createLinkedList(arr, n);
    printLinkedList(head);

    Solution().removeElements( head, 6);
    printLinkedList(head);

    deleteLinkedList( head );

    return 0;
}

82. Remove Duplicates from Sorted List II

给定一个有序链表,将其中有重复的元素全部删除。

  • 如1->2->3->3->4->4->5,返回1->2->5
  • 如1->1->1->2->3,返回2->3

21. Merge Two Sorted Lists

merge两个有序的链表

解题思路

如果能有链表的长度,就不用担心k非常大而不断的循环旋转了。所谓的旋转其实就是在链表中间断开,首尾相连。在获取链表长度的时候顺便把链表的首尾连起来。注意断开的位置是在倒数第k个之前。

解题思路

通过 Reverse Linked List 已经可以实现链表的翻转。看下图,把要翻转的一段先进行翻转,再把它和前后的链表接起来。因为可能要把第一个节点也进行翻转,为了一致性增加一个假的头节点。

图片 1

复杂的链表操作

24. Swap Nodes in Pairs

给定一个链表,对于每两个相邻的节点,交换其位置。

  • 如:链表为 1->2->3->4->NULL
  • 返回:2->1->4->3->NULL
  • 只能对节点进行操作,不能修改节点的值

虚拟头结点

虚拟头结点

next指针调整

核心在于创建几个指针预先保留。

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {

        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;

        ListNode* p = dummyHead;
        while( p->next && p->next->next ){
            ListNode* node1 = p->next;
            ListNode* node2 = node1->next;
            ListNode* next = node2->next;
            node2->next = node1;
            node1->next = next;
            p->next = node2;
            p = node1;
        }

        ListNode* retHead = dummyHead->next;
        delete dummyHead;

        return retHead;
    }
};

int main() {

    int arr[] = {1, 2, 3, 4};
    int n = sizeof(arr)/sizeof(int);

    ListNode* head = createLinkedList(arr, n);
    printLinkedList(head);

    head = Solution().swapPairs( head );
    printLinkedList(head);

    deleteLinkedList(head);

    return 0;
}

思考:可不可以不用next指针?

25. Reverse Nodes in k-Group

给定一个链表,每k个节点为一组,反转每一组的k个节点。k为正整数且小于等于链表长度。如果链表长度不是k的整数倍,剩余部分不需要进行反转。如: 1->2->3->4->5->NULL

  • 若 k = 2,则结果为:2->1->4->3->5->NULL
  • 若 k = 3,则结果为:3->2->1->4->5->NULL

147. Insertion Sort List

为一个链表进行插入排序

148. Sort List

写一个排序算法,用O(nlogn)的时间复杂度为一个链表进行排序

归并排序不需要使用数组索引:自底向上。

AC源码

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

    def myprint(self):
        print(self.val)
        if self.next:
            self.next.myprint()


class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if not head:
            return []
        curr = head
        length = 1
        while curr.next:
            curr = curr.next
            length  = 1
        curr.next = head
        cur = head
        shift = length - k % length
        while shift > 0:
            curr = curr.next
            shift -= 1
        result = curr.next
        curr.next = None
        return result


if __name__ == "__main__":
    l1 = ListNode(1)
    l2 = ListNode(2)
    l3 = ListNode(3)
    l4 = ListNode(4)
    l5 = ListNode(5)
    l1.next = l2
    l2.next = l3
    l3.next = l4
    l4.next = l5
    result = Solution().rotateRight(l1, 2)
    result.myprint()

Rotate List LeetCode解题之Rotate List 原题 将一个链表中的元素向右旋转k个位置。 注意点: k可能非常大 最好不要申请额外空间 例子:...

AC源码

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

    def to_list(self):
        return [self.val]   self.next.to_list() if self.next else [self.val]


class Solution(object):
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        dummy = ListNode(-1)
        dummy.next = head
        node = dummy
        for __ in range(m - 1):
            node = node.next
        prev = node.next
        curr = prev.next
        for __ in range(n - m):
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next
        node.next.next = curr
        node.next = prev
        return dummy.next


if __name__ == "__main__":
    n1 = ListNode(1)
    n2 = ListNode(2)
    n3 = ListNode(3)
    n4 = ListNode(4)
    n5 = ListNode(5)
    n1.next = n2
    n2.next = n3
    n3.next = n4
    n4.next = n5
    r = Solution().reverseBetween(n1, 2, 4)
    assert r.to_list() == [1, 4, 3, 2, 5]

Reverse Linked List II LeetCode解题之Reverse Linked List II 原题 在只遍历一遍且不申请额外空间的情况下将一个链表的第m到n个元素进行翻转。...

不仅仅是穿针引线

237. Delete Node in a Linked List

给定链表中的一个节点,删除该节点

class Solution {
public:
    void deleteNode(ListNode* node) {

    }
};

3赋值上4,然后把4的next保存。让第一个4指向第二个四的next

3赋值上4,然后把4的next保存。让第一个4指向第二个四的next

class Solution {
public:
    void deleteNode(ListNode* node) {

        assert(node != NULL && node->next != NULL);

        node->val = node->next->val;
        ListNode* delNode = node->next;
        node->next = delNode->next;

        delete delNode;

        return;
    }
};

特殊情况改变节点的值来实现我们需要的功能。

双指针技术

19. Remove Nth Node From End of List

给定一个链表,删除倒数第n个节点

  • 如:1->2->3->4->5->NULL, n = 2
  • 返回:1->2->3->5

n从0计还是从1计
n不合法,负数或者大于链表长度如何处理(保证n合法)

解法1:先遍历一遍计算链表长度;再遍历一遍删除倒数第n个节点
遍历两遍链表。能否只遍历一遍链表?

pq长度固定

具体实现:

// 先记录链表总长度
// 需要对链表进行两边遍历
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {

        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;

        int length = 0;
        for(ListNode* cur = dummyHead->next ; cur != NULL ; cur = cur->next )
            length   ;
        //cout<<length<<endl;

        int k = length - n;
        assert( k >= 0 );
        ListNode* cur = dummyHead;
        for( int i = 0 ; i < k ; i    )
            cur = cur -> next;

        ListNode* delNode = cur->next;
        cur->next = delNode->next;
        delete delNode;

        ListNode* retNode = dummyHead->next;
        delete dummyHead;
        return retNode;
    }
};

使用双指针:

// 使用双指针, 对链表只遍历了一遍
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {

        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;

        ListNode* p = dummyHead;
        ListNode* q = dummyHead;
        for( int i = 0 ; i < n   1 ; i    ){
            assert(q);
            q = q->next;
        }

        while( q ){
            p = p->next;
            q = q->next;
        }

        ListNode* delNode = p->next;
        p->next = delNode->next;
        delete delNode;

        ListNode* retNode = dummyHead->next;
        delete dummyHead;

        return retNode;
    }
};

61. Rotate List

给定一个链表,让这个链表向右旋转k位。其中k为非负数。

  • 如:1->2->3->4->5->NULL, k = 2
  • 第一次旋转:5->1->2->3->4->NULL
  • 第二次旋转:4->5->1->2->3->NULL

143. Reorder List

给定一个链表 L(0) -> L(1) -> L(2) -> … -> L(n-1) -> L(n)
将其变为 L(0) -> L(n) -> L(1) -> L(n-1) -> L(2) -> L(n-2)…
的形式

  • 链表无法随机访问数据,如何获得中间的元素?
  • 两次遍历?一次遍历?

234. Palindrome Linked List

给一个链表,判断这个链表是否为回文(正看反看)链表。

  • 能否使用O(1)的空间复杂度解决问题?

本文由9159.com发布于编程,转载请注明出处:给出索引,k可能非常大 最好不要申请额外空间

关键词: 9159.com

上一篇:初始化的工作包括,2.游戏界面类
下一篇:没有了