Tags » Linked List

[LeetCode] Partition List

题目:
划分一个链表,小于x的赶到左边,大于等于x的赶到右边
https://leetcode.com/problems/partition-list/

解法:
把小于x的串在一起,把大于等于x的串在一起,然后粘起来

Java代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null) {
            return null;
        }
        
        ListNode small = new ListNode(0), big = new ListNode(0);
        ListNode smallPrev = small, bigPrev = big;
        ListNode cur = head;
        
        while(cur != null) {
            if (cur.val < x) {
                smallPrev.next = cur;
                smallPrev = cur;
            } else {
                bigPrev.next = cur;
                bigPrev = cur;
            }
            cur = cur.next;
        }
        
        bigPrev.next = null;
        smallPrev.next = big.next;
        
        return small.next;
    }
}

[LeetCode] Odd Even Linked List

题目:
给定一个链表,把odd node赶到左边,even node赶到右边。odd,even指的是node的下标,而不是node的value
https://leetcode.com/problems/odd-even-linked-list/

解法:
跟标准解法不一样,我把odd node串在一起,even node串在一起,然后把两个list粘起来。

Java代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode oddEvenList(ListNode head) {
        ListNode dummyOddHead = new ListNode(0), dummyEvenHead = new ListNode(0);
        ListNode oddPrev = dummyOddHead, evenPrev = dummyEvenHead;
        ListNode cur = head;
        boolean odd = true;
        
        while(cur != null) {
            if (odd) {
                oddPrev.next = cur;
                oddPrev = cur;
            } else {
                evenPrev.next = cur;
                evenPrev = cur;
            }
            
            odd = !odd;
            cur = cur.next;
        }
        
        if(!odd) {
            evenPrev.next = null;
        }
        
        oddPrev.next = dummyEvenHead.next;
        
        return dummyOddHead.next;
    }
}

Stack - Implementation

Introduction

Stack is a very common data structures which will return in the element stored in a Last In First Out fashion.

Applications

Arrays

25. Reverse Nodes in k-Group

Difficulty: Hard

Frequency: N/A

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. 183 more words

Leetcode

LinkedLists Algorithms

How to Append a Node at the head of LinkedList?


public class MyLinkedList {
	public static void main(String[] args) {
		Node a = new Node(1);
		Node b = new Node(2);
		Node c = new Node(3);
		a.next=b;
		b.next=c;
		a.printList();
		System.out.println("After adding new node");
		Node newNode = appendANodeAtHead(a,4);
		newNode.printList();
		
}
private static Node appendANodeAtHead(Node head, int data){
	Node newNode = new Node(data);
	newNode.next= head;
	return newNode;
}
static class Node{
	Node next;
	int data;
	Node(int d){
	this.data=d;
	}
	public void printList(){
	Node current=this;
	while(current!=null){
		System.out.println(current.data+"->");
		current = current.next;
		}
		System.out.println();
			
	}
}
… 290 more words
Linked List

【287】Find the Duplicate Number

题目:给一个含有 n + 1 个正整数数组 nums[],每个元素的取值是 的正整数。按照鸽巢远离,至少有一个元素是重复的。假设只有一个元素是重复的,并且也许可能重复超过 2 次。找出这个正整数

算法:2 pointers,用 linked list 来模拟

思路:

  • (我是看过别人家的答案才整理的)
  • nums[i] = j, nums[j] = k, nums[k] = l,就相当于 node i -> node j -> node k -> node l…
  • 81 more words
Leetcode

023. Merge k Sorted Lists

Difficulty: Hard

Frequency: N/A

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

My solution:

Data structure: 120 more words

Leetcode