Maximizing Mission Points
Problem Statement :
Xander Cage has a list of cities he can visit on his new top-secret mission. He represents each city as a tuple of . The values of , , and are distinct across all cities. We define a mission as a sequence of cities, , that he visits. We define the total of such a mission to be the sum of the of all the cities in his mission list. Being eccentric, he abides by the following rules on any mission: He can choose the number of cities he will visit (if any). He can start the mission from any city. He visits cities in order of strictly increasing . The absolute difference in between adjacent visited cities in his mission must be at most . The absolute difference in between adjacent visited cities in his mission must be at most . Given , , and the definitions for cities, find and print the maximum possible total that Xander can earn on a mission. Input Format The first line contains three space-separated integers describing the respective values of , , and . Each line of the subsequent lines contains four space-separated integers denoting the respective , , , and for a city. Constraints Output Format Print a single integer denoting the maximum possible that Xander can earn on a mission.
Solution :
Solution in C :
In C :
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _tree{
int *y;
long long *a;
int size;
int N;
int *left_idx;
int *right_idx;
} tree;
int diff(int x,int y);
long long max(long long x,long long y);
void init(int n,int *N);
long long range_sum( int i, int j);
void updatea(int i);
void build(int v);
void merge(tree *t,tree *x,tree *y);
int get_i(int*a,int num,int size);
int med(int*a,int size);
long long query(int v);
void update(int v,int idx);
int x1,x2,y1,y2,N,tl[800000],tr[800000];
long long val,*tt;
int lat[200000]={0},lon[200000]={0},poi[200000],tla[200000]={0};
tree t[800000];
int main(){
int n,x,y,c,i,j,max_idx=-1,a,b,C,d;
long long max=0,dp;
scanf("%d%d%d",&n,&x,&y);
for(i=c=0;i<n;i++){
scanf("%d%d%d%d",&a,&b,&C,&d);
if(d>0)
c++;
lat[C-1]=a;
lon[C-1]=b;
poi[C-1]=d;
tla[a-1]=b;
}
if(!c){
printf("0");
return 0;
}
tl[1]=0;
tr[1]=199999;
build(1);
for(i=199999;i>=0;i--)
if(lat[i]){
if(max_idx!=-1 && diff(lat[max_idx],lat[i])<=x && diff(lon[max_idx],lon[i])<=y)
dp=max;
else{
x1=lat[i]-x-1;
x2=lat[i]+x-1;
y1=lon[i]-y;
y2=lon[i]+y;
dp=query(1);
}
if(dp>0)
dp+=poi[i];
else
dp=poi[i];
if(dp>max){
max=dp;
max_idx=i;
}
if(dp>0){
x1=lat[i]-1;
y1=lon[i];
val=dp;
update(1,-1);
}
}
printf("%lld",max);
return 0;
}
int diff(int x,int y){
return (x<y)?(y-x):(x-y);
}
long long max(long long x,long long y){
return (x>y)?x:y;
}
void init(int n,int *N){
(*N) = 1;
while( (*N) < n ) (*N) *= 2;
}
long long range_sum( int i, int j){
long long ans = 0;
for( i += N, j += N; i <= j; i = ( i + 1 ) / 2, j = ( j - 1 ) / 2 )
{
if( i % 2 == 1 ) ans = max(ans,tt[i]);
if( j % 2 == 0 ) ans = max(ans,tt[j]);
}
return ans;
}
void updatea(int i){
int j;
for( j = i + N; j; j /= 2 ) tt[j] = max(tt[j],val);
}
void build(int v){
if(tl[v]==tr[v]){
t[v].size=1;
t[v].y=(int*)malloc(t[v].size*sizeof(int));
t[v].a=(long long*)malloc(4*t[v].size*sizeof(long long));
memset(t[v].a,0,4*t[v].size*sizeof(long long));
t[v].y[0]=tla[tl[v]];
init(t[v].size,&t[v].N);
}
else{
int tm=(tl[v]+tr[v])/2;
tl[2*v]=tl[v];
tl[2*v+1]=tm+1;
tr[2*v]=tm;
tr[2*v+1]=tr[v];
build(v*2);
build(v*2+1);
merge(&t[v],&t[v*2],&t[v*2+1]);
}
return;
}
void merge(tree *t,tree *x,tree *y){
int i=0,j=0;
t->size=x->size+y->size;
t->y=(int*)malloc(t->size*sizeof(int));
t->left_idx=(int*)malloc(t->size*sizeof(int));
t->right_idx=(int*)malloc(t->size*sizeof(int));
t->a=(long long*)malloc(t->size*sizeof(long long)*4);
memset(t->a,0,t->size*sizeof(long long)*4);
init(t->size,&t->N);
while(i<x->size || j<y->size){
if(i==x->size){
t->y[i+j]=y->y[j];
t->left_idx[i+j]=i-1;
t->right_idx[i+j]=j;
j++;
}
else if(j==y->size){
t->y[i+j]=x->y[i];
t->left_idx[i+j]=i;
t->right_idx[i+j]=j-1;
i++;
}
else if(x->y[i]<=y->y[j]){
t->y[i+j]=x->y[i];
t->left_idx[i+j]=i;
t->right_idx[i+j]=j-1;
i++;
}
else{
t->y[i+j]=y->y[j];
t->left_idx[i+j]=i-1;
t->right_idx[i+j]=j;
j++;
}
}
return;
}
int get_i(int*a,int num,int size){
if(size==0)
return 0;
if(num>med(a,size))
return get_i(&a[(size+1)>>1],num,size>>1)+((size+1)>>1);
else
return get_i(a,num,(size-1)>>1);
}
int med(int*a,int size){
return a[(size-1)>>1];
}
long long query(int v){
int i,j;
if(tl[v]>x2 || tr[v]<x1 || !t[v].a[1])
return 0;
if(tl[v]>=x1 && tr[v]<=x2){
i=get_i(t[v].y,y1,t[v].size);
j=get_i(t[v].y,y2+1,t[v].size)-1;
if(j<i)
return 0;
N=t[v].N;
tt=t[v].a;
return range_sum(i,j);
}
else if(tl[v]!=tr[v])
return max(query(2*v),query(2*v+1));
return 0;
}
void update(int v,int idx){
if(tl[v]<=x1 && tr[v]>=x1){
if(idx==-1)
idx=get_i(t[v].y,y1,t[v].size);
N=t[v].N;
tt=t[v].a;
updatea(idx);
if(tl[v]!=tr[v]){
update(v*2,t[v].left_idx[idx]);
update(v*2+1,t[v].right_idx[idx]);
}
}
return;
}
Solution in C++ :
In C++ :
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
#define forn(i, n) for (int i = 0; i < int(n); ++i)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef vector<pii> vii;
#define sz(c) (int)(c).size()
#define ALL(c) (c).begin(), (c).end()
struct town
{
int x, y, h, p;
bool operator < (const town &o) const
{
return h < o.h;
}
};
struct segtree
{
vll vals;
int tsz;
segtree ()
{
vals.clear();
tsz = 0;
}
segtree (int n)
{
tsz = 1;
while (tsz <= n)
tsz *= 2;
vals.assign(2 * tsz, 0);
}
void put (int pos, ll what)
{
for (pos += tsz; pos > 0; pos >>= 1)
vals[pos] = max(vals[pos], what);
}
ll query (int l, int r)
{
ll ans = 0;
for (l += tsz, r += tsz; l < r; l >>= 1, r >>= 1)
{
if (l & 1)
ans = max(ans, vals[l++]);
if (r & 1)
ans = max(ans, vals[--r]);
}
return ans;
}
};
struct segtree2d
{
vvi who;
vector<segtree> data;
int tsz;
segtree2d (const vii &ps)
{
int X = 0;
const int n = sz(ps);
forn (i, n) X = max(X, ps[i].fst);
tsz = 1;
while (tsz <= X)
tsz *= 2;
data.resize(2 * tsz);
who.resize(2 * tsz);
forn (i, n)
who[ps[i].fst + tsz].pb(ps[i].snd);
for (int i = tsz; i < 2 * tsz; i++)
data[i] = segtree(sz(who[i]));
for (int i = tsz - 1; i >= 1; i--)
{
who[i].resize(sz(who[2 * i]) + sz(who[2 * i + 1]));
merge(ALL(who[2 * i]), ALL(who[2 * i + 1]), who[i].begin());
data[i] = segtree(sz(who[i]));
}
}
ll query (int v, int d, int u)
{
int rd = lower_bound(ALL(who[v]), d) - who[v].begin();
int ru = lower_bound(ALL(who[v]), u) - who[v].begin();
return data[v].query(rd, ru);
}
ll query (int l, int r, int d, int u)
{
r = min(r, tsz);
ll ans = 0;
for (l += tsz, r += tsz; l < r; l >>= 1, r >>= 1)
{
if (l & 1)
ans = max(ans, query(l++, d, u));
if (r & 1)
ans = max(ans, query(--r, d, u));
}
return ans;
}
void putnode (int v, int pos, ll what)
{
int cur = lower_bound(ALL(who[v]), pos) - who[v].begin();
assert(cur != sz(who[v]) && who[v][cur] == pos);
data[v].put(cur, what);
}
void put (int x, int y, ll what)
{
for (x += tsz; x > 0; x >>= 1)
putnode(x, y, what);
}
};
void solve (int n)
{
int mx, my;
cin >> mx >> my;
vector<town> v(n);
forn (i, n)
cin >> v[i].x >> v[i].y >> v[i].h >> v[i].p;
sort(ALL(v));
vii ps(n);
forn (i, n) ps[i] = mp(v[i].x, v[i].y);
segtree2d data(ps);
vll dp(n);
forn (i, n)
{
int cx = v[i].x, cy = v[i].y;
int lx = max(0, cx - mx), ly = max(0, cy - my);
int rx = cx + mx, ry = cy + my;
dp[i] = data.query(lx, rx + 1, ly, ry + 1) + v[i].p;
data.put(cx, cy, dp[i]);
}
ll ans = max(0LL, *max_element(ALL(dp)));
cout << ans << endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
while (cin >> n)
solve(n);
}
Solution in Java :
In Java :
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class D {
InputStream is;
PrintWriter out;
String INPUT = "";
void solve()
{
int n = ni();
int x = ni(), y = ni();
int[][] co = new int[n][];
for(int i = 0;i < n;i++){
co[i] = new int[]{ni(), ni(), ni(), ni()};
}
// Arrays.sort(co, new Comparator<int[]>() {
// public int compare(int[] a, int[] b) {
// return a[2] - b[2];
// }
// });
StaticRangeTreeRMQ2 st = new StaticRangeTreeRMQ2(co, 200005);
// for(int i = 0;i < n;i++){
// st.update(co[i][0], co[i][1], Long.MAX_VALUE / 2);
// }
mergesort(co, 0, n);
long max = Long.MIN_VALUE;
long[] dp = new long[n];
for(int i = 0;i < n;i++){
long min = -st.min(co[i][0]-x, co[i][0]+x+1, co[i][1]-y, co[i][1]+y+1);
long val = co[i][3] + Math.max(min, 0);
dp[i] = val;
st.update(co[i][0], co[i][1], -dp[i]);
max = Math.max(max, dp[i]);
}
out.println(max);
}
private static int[][] stemp = new int[200005][];
public static void mergesort(int[][] a, int s, int e)
{
if(e - s <= 1)return;
int h = s+e>>1;
mergesort(a, s, h);
mergesort(a, h, e);
int p = 0;
int i= s, j = h;
for(;i < h && j < e;)stemp[p++] = a[i][2] < a[j][2] ? a[i++] : a[j++];
while(i < h)stemp[p++] = a[i++];
while(j < e)stemp[p++] = a[j++];
System.arraycopy(stemp, 0, a, s, e-s);
}
public static void mergesort0(int[][] a, int s, int e)
{
if(e - s <= 1)return;
int h = s+e>>1;
mergesort0(a, s, h);
mergesort0(a, h, e);
int p = 0;
int i= s, j = h;
for(;i < h && j < e;)stemp[p++] = a[i][0] < a[j][0] || a[i][0] == a[j][0] && a[i][1] < a[j][1] ? a[i++] : a[j++];
while(i < h)stemp[p++] = a[i++];
while(j < e)stemp[p++] = a[j++];
System.arraycopy(stemp, 0, a, s, e-s);
}
public static class StaticRangeTreeRMQ2 {
public int M, H, N;
public SegmentTreeRMQL[] st;
public int[][] maps;
public long[][] vals;
public int[] count;
public long I = Long.MAX_VALUE;
public StaticRangeTreeRMQ2(int[][] co, int n)
{
N = n;
M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
H = M>>>1;
mergesort0(co, 0, co.length);
// Arrays.sort(co, new Comparator<int[]>() { // x asc
// public int compare(int[] a, int[] b) {
// if(a[0] != b[0])return a[0] - b[0];
// return a[1] - b[1];
// }
// });
maps = new int[M][];
vals = new long[M][];
st = new SegmentTreeRMQL[M];
count = new int[M];
for(int i = 0;i < co.length;i++){
count[H+co[i][0]]++;
}
int off = 0;
for(int i = 0;i < n;i++){
maps[H+i] = new int[count[H+i]];
for(int j = 0;j < count[H+i];j++,off++){
maps[H+i][j] = co[off][1];
}
st[H+i] = new SegmentTreeRMQL(count[H+i]);
}
for(int i = H-1;i >= 1;i--){
if(maps[2*i+1] == null){
maps[i] = maps[2*i];
count[i] = count[2*i];
}else{
count[i] = count[2*i] + count[2*i+1];
maps[i] = new int[count[i]];
int l = 0;
for(int j = 0, k = 0;j < count[2*i] || k < count[2*i+1];l++){
if(j == count[2*i]){
maps[i][l] = maps[2*i+1][k++];
}else if(k == count[2*i+1]){
maps[i][l] = maps[2*i][j++];
}else if(maps[2*i][j] < maps[2*i+1][k]){
maps[i][l] = maps[2*i][j++];
}else if(maps[2*i][j] > maps[2*i+1][k]){
maps[i][l] = maps[2*i+1][k++];
}else{
maps[i][l] = maps[2*i][j++];
k++;
}
}
if(l != count[i]){ // uniq
count[i] = l;
maps[i] = Arrays.copyOf(maps[i], l);
}
}
if(count[i] <= 25){ // 10% faster
vals[i] = new long[count[i]];
Arrays.fill(vals[i], Long.MAX_VALUE / 2);
}else{
st[i] = new SegmentTreeRMQL(count[i]);
}
}
}
public void update(int x, int y, long v)
{
outer:
for(int pos = H+x;pos >= 1;pos>>>=1){
if(st[pos] != null){
int ind = Arrays.binarySearch(maps[pos], y);
if(ind >= 0){
st[pos].update(ind, v);
continue;
}
}else{
for(int i = 0;i < count[pos];i++){
if(maps[pos][i] == y){
vals[pos][i] = v;
continue outer;
}
}
}
throw new RuntimeException(String.format("access to non-existing point : (%d,%d):%d", x, y, v));
}
}
public long min(int xl, int xr, int yl, int yr) { return min(xl, xr, yl, yr, 0, H, 1); }
public long min(int xl, int xr, int yl, int yr, int cl, int cr, int cur)
{
if(xl <= cl && cr <= xr){
if(st[cur] != null){
int indl = Arrays.binarySearch(maps[cur], yl);
int indr = Arrays.binarySearch(maps[cur], yr);
if(indl < 0)indl = -indl - 1;
if(indr < 0)indr = -indr - 1;
return st[cur].minx(indl, indr);
}else{
long min = I;
for(int i = 0;i < count[cur] && maps[cur][i] < yr;i++){
if(maps[cur][i] >= yl && vals[cur][i] < min) min = vals[cur][i];
}
return min;
}
}else{
int mid = cl+cr>>>1;
long ret = I;
if(cl < xr && xl < mid)ret = Math.min(ret, min(xl, xr, yl, yr, cl, mid, 2*cur));
if(mid < xr && xl < cr)ret = Math.min(ret, min(xl, xr, yl, yr, mid, cr, 2*cur+1));
return ret;
}
}
}
public static class SegmentTreeRMQL {
public int M, H, N;
public long[] st;
public SegmentTreeRMQL(int n)
{
N = n;
M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
H = M>>>1;
st = new long[M];
Arrays.fill(st, 0, M, Long.MAX_VALUE/2);
}
public SegmentTreeRMQL(long[] a)
{
N = a.length;
M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
H = M>>>1;
st = new long[M];
for(int i = 0;i < N;i++){
st[H+i] = a[i];
}
Arrays.fill(st, H+N, M, Long.MAX_VALUE);
for(int i = H-1;i >= 1;i--)propagate(i);
}
public void update(int pos, long x)
{
st[H+pos] = x;
for(int i = (H+pos)>>>1;i >= 1;i >>>= 1)propagate(i);
}
private void propagate(int i)
{
st[i] = Math.min(st[2*i], st[2*i+1]);
}
public long minx(int l, int r){
long min = Long.MAX_VALUE;
if(l >= r)return min;
while(l != 0){
int f = l&-l;
if(l+f > r)break;
long v = st[(H+l)/f];
if(v < min)min = v;
l += f;
}
while(l < r){
int f = r&-r;
long v = st[(H+r)/f-1];
if(v < min)min = v;
r -= f;
}
return min;
}
public long min(int l, int r){ return l >= r ? 0 : min(l, r, 0, H, 1);}
private long min(int l, int r, int cl, int cr, int cur)
{
if(l <= cl && cr <= r){
return st[cur];
}else{
int mid = cl+cr>>>1;
long ret = Long.MAX_VALUE;
if(cl < r && l < mid){
ret = Math.min(ret, min(l, r, cl, mid, 2*cur));
}
if(mid < r && l < cr){
ret = Math.min(ret, min(l, r, mid, cr, 2*cur+1));
}
return ret;
}
}
public int firstle(int l, long v) {
int cur = H+l;
while(true){
if(st[cur] <= v){
if(cur < H){
cur = 2*cur;
}else{
return cur-H;
}
}else{
cur++;
if((cur&cur-1) == 0)return -1;
if((cur&1)==0)cur>>>=1;
}
}
}
public int lastle(int l, long v) {
int cur = H+l;
while(true){
if(st[cur] <= v){
if(cur < H){
cur = 2*cur+1;
}else{
return cur-H;
}
}else{
if((cur&cur-1) == 0)return -1;
cur--;
if((cur&1)==1)cur>>>=1;
}
}
}
}
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
}
public static void main(String[] args) throws Exception { new D().run(); }
private byte[] inbuf = new byte[1024];
public int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
Solution in Python :
In Python3 :
from collections import namedtuple
from bisect import bisect_left
import sys
Place = namedtuple('Place', 'lat, long, height, points')
chunkplaces={} # places get inserted into lists contained here, grouped by keys of their locations
chunkvals={} # holds values
giant = False
def getkey(place, off_lat=0, off_long=0):
return ((place.lat // d_lat + off_lat) * 200011) + place.long // d_long + off_long # unique for n<=200000
def recordvalue(place, val):
if val < 0:
return # not worth going here; no need to track
key = getkey(place)
if key not in chunkplaces:
chunkplaces[key] = []
chunkvals[key] = []
if giant:
if len(chunkvals[key]) == 0:
chunkvals[key].append(-val)
chunkplaces[key].append(place)
else:
if val < -chunkvals[key][0]:
return
else:
chunkvals[key][0] = -val
chunkplaces[key][0] = place
else:
i = bisect_left(chunkvals[key], -val)
chunkplaces[key].insert(i, place)
chunkvals[key].insert(i, -val)
# print(i, val, [val for val in chunkvals[key]])
def getbestinchunk(place, key, best):
# find best suitable match in chunk
if key not in chunkvals:
return 0
for i, (cand, val) in enumerate(zip(chunkplaces[key], chunkvals[key])):
# print("evaluating %s"%cand)
if -val < best:
# this is the best we have, but it's not as good as we've seen other places; abort
return 0
if abs(place.lat - cand.lat) <= d_lat \
and abs(place.long - cand.long) <= d_long :
# and cand.height > place.height: # height is given, assuming they're unique
# suitable, return it
return -val
# no suitable match
return 0
def getbest(place):
# find best match in this and neighboring chunks, then pick the best
best = 0 # always have the option to stop here
for i in [0,1,-1]:
for j in [0,1,-1]:
key = getkey(place, i, j)
ret = getbestinchunk(place, key, best)
if ret > best:
best = ret
return best
def calculatevalue(place):
val = place.points + getbest(place)
recordvalue(place, val)
return val
if __name__ == "__main__":
n, d_lat, d_long = input().strip().split(' ')
n, d_lat, d_long = [int(n), int(d_lat), int(d_long)]
places = []
if d_lat == 200000:
giant = True
for a0 in range(n):
latitude, longitude, height, points = input().strip().split(' ')
latitude, longitude, height, points = [int(latitude), int(longitude), int(height), int(points)]
places.append(Place(latitude, longitude, height, points))
places.sort(key=lambda p: -p.height) # compute highest first
best = 0
for p in places:
ret = calculatevalue(p)
if ret > best:
best = ret
print(best)
View More Similar Problems
Reverse a linked list
Given the pointer to the head node of a linked list, change the next pointers of the nodes so that their order is reversed. The head pointer given may be null meaning that the initial list is empty. Example: head references the list 1->2->3->Null. Manipulate the next pointers of each node in place and return head, now referencing the head of the list 3->2->1->Null. Function Descriptio
View Solution →Compare two linked lists
You’re given the pointer to the head nodes of two linked lists. Compare the data in the nodes of the linked lists to check if they are equal. If all data attributes are equal and the lists are the same length, return 1. Otherwise, return 0. Example: list1=1->2->3->Null list2=1->2->3->4->Null The two lists have equal data attributes for the first 3 nodes. list2 is longer, though, so the lis
View Solution →Merge two sorted linked lists
This challenge is part of a tutorial track by MyCodeSchool Given pointers to the heads of two sorted linked lists, merge them into a single, sorted linked list. Either head pointer may be null meaning that the corresponding list is empty. Example headA refers to 1 -> 3 -> 7 -> NULL headB refers to 1 -> 2 -> NULL The new list is 1 -> 1 -> 2 -> 3 -> 7 -> NULL. Function Description C
View Solution →Get Node Value
This challenge is part of a tutorial track by MyCodeSchool Given a pointer to the head of a linked list and a specific position, determine the data value at that position. Count backwards from the tail node. The tail is at postion 0, its parent is at 1 and so on. Example head refers to 3 -> 2 -> 1 -> 0 -> NULL positionFromTail = 2 Each of the data values matches its distance from the t
View Solution →Delete duplicate-value nodes from a sorted linked list
This challenge is part of a tutorial track by MyCodeSchool You are given the pointer to the head node of a sorted linked list, where the data in the nodes is in ascending order. Delete nodes and return a sorted list with each distinct value in the original list. The given head pointer may be null indicating that the list is empty. Example head refers to the first node in the list 1 -> 2 -
View Solution →Cycle Detection
A linked list is said to contain a cycle if any node is visited more than once while traversing the list. Given a pointer to the head of a linked list, determine if it contains a cycle. If it does, return 1. Otherwise, return 0. Example head refers 1 -> 2 -> 3 -> NUL The numbers shown are the node numbers, not their data values. There is no cycle in this list so return 0. head refer
View Solution →